题目描述

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=0.5,1.5,2.5,\cdots,(N−1).5$ , 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$.

In particular, Bessie's route can be represented by a string of $T=\sum\limits_{i=0}^{N-1}A_i$ Ls 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.

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 $A_0,A_1, \cdots ,A_{N−1}$.

输出格式

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

2
4 6

2

提示

Explanation for Sample 1

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

$\texttt{RRLRLLRRLL}$
$\texttt{RRLLRRLRLL}$

Scoring

• Inputs $2-4$: $N \le 2$ and $\max(A_i) \le 10^3$
• Inputs $5-7$: $N \le 2$
• Inputs $8-11$: $\max(A_i) \le 10^3$
• Inputs $12-21$: No additional constraints.