Minimal Direction Changes in Bessie's Route

Farmer Nhoj dropped Bessie in the middle of nowhere! At time \(t=0\), Bessie is located at \(x=0\) on an infinite number line. Every second she moves either left or right by \(1\) unit. After \(T=\sum_{i=0}^{N-1}A_i\) seconds she returns to \(x=0\), tired and resigned.

Farmer Nhoj only knows how many times Bessie crosses the points \(x=0.5,\,1.5,\,2.5,\,\dots,\,(N-1).5\) as given by an array \(A_0,A_1,\dots,A_{N-1}\). It is guaranteed that Bessie never reaches \(xN\). Observe that every time Bessie crosses the line \(x=i+0.5\) (for \(0\le i\le N-1\)) she is effectively performing an excursion between positions \(i\) and \(i+1\). Define \[ k_i=\frac{A_i}{2} \quad (0\le i\le N-1), \] so that \(k_i\) counts the number of complete excursions across the boundary between \(i\) and \(i+1\).

Bessie's route is represented by a string of \(T\) characters, each being L or R. The number of direction changes is defined as the count of occurrences of LR and RL as substrings. Among all routes that are consistent with the crossing counts \(A\), Bessie chooses one that minimizes the number of direction changes. It can be shown that the total number of such minimal‐change routes is given by

\[ \prod_{i=0}^{N-2} \binom{k_i}{k_{i+1}}, \]

with the convention that when \(N=1\) the answer is \(1\). Your task is to compute and output this number.

inputFormat

The first line contains a single integer \(N\) (\(1\le N\le10^5\)).

The second line contains \(N\) space-separated integers \(A_0, A_1, \dots, A_{N-1}\) (\(1\le A_i\le10^6\)).

It is guaranteed that there exists at least one valid route.

outputFormat

Output a single integer: the number of routes Bessie could have taken that are consistent with \(A\) and have the minimum number of direction changes.

sample

1
2

1