Difficulty-Based Problem Selection
Time limit1sMemory limit128 MB
Count ways to pick exactly one problem per difficulty level 1..N given fixed-difficulty and flexible dual-difficulty problem pools, modulo 1e9+7.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math
- Solved
- No attempts yet
Problem
A contest needs exactly one problem for each difficulty from 1 through N.
There are A_i problems whose difficulty is exactly i. For each i with 1 <= i < N, there are B_i problems whose difficulty may be either i or i+1. The same problem cannot be used more than once. If a problem has two possible difficulties, choosing it also assigns it to one of those two difficulties.
Two selections are different if at least one difficulty is assigned a different actual problem. Compute the number of valid selections modulo 1,000,000,007.
Input
The first line contains an integer N (2 <= N <= 100,000).
The second line contains N integers A_1, A_2, ..., A_N. A_i is the number of problems whose difficulty is exactly i, and each value is a nonnegative integer at most 10^9.
The third line contains N-1 integers B_1, B_2, ..., B_{N-1}. B_i is the number of problems whose difficulty may be either i or i+1, and each value is a nonnegative integer at most 10^9.
Output
Print the number of valid selections modulo 1,000,000,007.