{"raw_statement":[{"iden":"statement","content":"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.\n\nFarmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5,\\cdots,(N−1).5$\n, given by an array $A_0,A_1, \\cdots ,A_{N−1} (1 \\le N \\le 10^5, 1 \\le A_i \\le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.\n\nIn particular, Bessie's route can be represented by a string of $T=\\sum\\limits_{i=0}^{N-1}A_i$\nLs and Rs where the ith character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.\n\nPlease help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with $A$\nand minimize the number of direction changes. It is guaranteed that there is at least one valid route. "},{"iden":"input","content":"The first line contains $N$. The second line contains $A_0,A_1, \\cdots ,A_{N−1}$. "},{"iden":"output","content":"The number of routes Bessie could have taken, modulo $10^9+7$. "},{"iden":"note","content":"### Explanation for Sample 1\n\nBessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times: \n\n$\\texttt{RRLRLLRRLL}$  \n$\\texttt{RRLLRRLRLL}$\n\n### Scoring\n\n - Inputs $2-4$: $N \\le 2$ and $\\max(A_i) \\le 10^3$\n - Inputs $5-7$: $N \\le 2$\n - Inputs $8-11$: $\\max(A_i) \\le 10^3$\n - Inputs $12-21$: No additional constraints."}],"translated_statement":null,"sample_group":[["2\n4 6","2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}