Moo Route

문제

Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0t=0$, Bessie is located at $x=0x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $11$ unit each second. However, there actually is no exit and after $TT$ seconds, Bessie is back at $x=0x=0$, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=.5,1.5,2.5,\dots ,(N-1).5x=.5,\; 1.5,\; 2.5,\; \backslash ldots,\; (N-1).5$, given by an array $A_0,A_1,\dots ,A_{N-1}A\_0,A\_1,\backslash dots,A\_\{N-1\}$ ($1\le N\le {10}^{5}1\backslash leq\; N\; \backslash leq\; 10^5$, $1\le A_i\le {10}^{6}1\; \backslash leq\; A\_i\; \backslash leq\; 10^6$). Bessie never reaches $x>Nx>N$ nor .

In particular, Bessie's route can be represented by a string of $T={\sum }_{i=0}^{N-1}{A}_{i}T\; =\; \backslash sum\_\{i=0\}^\{N-1\}\; A\_i$ $LL$s and $RR$s where the $ii$th character represents the direction Bessie moves in during the $ii$th second. The number of direction changes is defined as the number of occurrences of $LRLR$s plus the number of occurrences of $RLRL$s.

Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with $AA$ and minimize the number of direction changes. It is guaranteed that there is at least one valid route.

입력

The first line contains $NN$. The second line contains $A_0,A_1,\dots ,A_{N-1}A\_0,A\_1,\backslash dots,A\_\{N-1\}$.

출력

The number of routes Bessie could have taken, modulo ${10}^9+710^9+7$.

힌트

Bessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times:

RRLRLLRRLL
RRLLRRLRLL

2
4 6

2