문제
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 A0,A1,…,AN−1 (1≤N≤105, 1≤Ai≤106). Bessie never reaches x>N nor x<0.
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.
입력
The first line contains N. The second line contains A0,A1,…,AN−1.
출력
The number of routes Bessie could have taken, modulo 109+7.
예제1
2
4 6
2