8170: USACO 2023 January Contest, Gold Problem 3. Moo Route
[Creator : ]
Description
Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0, Bessie is located at x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 1 unit each second. However, there actually is no exit and after T seconds, Bessie is back at x=0, tired and resigned.
Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5, given by an array $A_0,A_1,…,A_{N−1}\ (1≤N≤10^5,\ 1≤A_i≤10^6)$. Bessie never reaches x>N nor x<0.
In particular, Bessie's route can be represented by a string of $T=\sum_{i=0}^{N−1} {A_i}$ Ls and Rs where the i-th character represents the direction Bessie moves in during the i-th second. The number of direction changes is defined as the number of occurrences of LRs plus the number of occurrences of RLs.
Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with A and minimize the number of direction changes. It is guaranteed that there is at least one valid route.
Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5, given by an array $A_0,A_1,…,A_{N−1}\ (1≤N≤10^5,\ 1≤A_i≤10^6)$. Bessie never reaches x>N nor x<0.
In particular, Bessie's route can be represented by a string of $T=\sum_{i=0}^{N−1} {A_i}$ Ls and Rs where the i-th character represents the direction Bessie moves in during the i-th second. The number of direction changes is defined as the number of occurrences of LRs plus the number of occurrences of RLs.
Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with A and minimize the number of direction changes. It is guaranteed that there is at least one valid route.
Input
The first line contains N.
The second line contains $A_0,A_1,…,A_{N−1}$.
The second line contains $A_0,A_1,…,A_{N−1}$.
Output
The number of routes Bessie could have taken, modulo $10^9+7$.
Sample 1 Input
2
4 6
Sample 1 Output
2
Bessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times:
RRLRLLRRLL
RRLLRRLRLL