Painting Walls

Little Blue is a hardworking painter. Today he received an order from Lanqiao College to paint n walls arranged from left to right and numbered from \(1\) to \(n\). Initially, all walls are white. The college wishes to create a cool artistic atmosphere by painting some walls blue. To that end, an array \(\{a_1, a_2, \cdots, a_n\}\) of length \(n\) is provided. Specifically, if \(a_i=0\), then wall \(i\) remains white; if \(a_i=1\), then wall \(i\) must be painted blue.

Little Blue paints one wall at a time; he never partially paints a wall. In addition, during the painting process, whenever he paints a wall \(i\) blue, the number of walls to its right (i.e. walls \(i+1, i+2, \ldots, n\)) that are required to be blue and have not yet been painted must be even (note that \(0\) is considered even).

Your task is to calculate the number of painting orders that satisfy the college’s requirement. Two orders are considered different if the sequence in which the walls are painted differs. Since the answer may be very large, output it modulo \(10^9+7\).

Explanation

Let \(k\) be the number of walls that must be painted blue (i.e. \(k\) is the number of ones in the array). The restriction only affects the relative order in which the blue walls are painted. One can show that the number of valid orders for the blue walls is \[ f(k)=\begin{cases}1 & \text{if } k\le1,\\2^{k-2} & \text{if } k\ge2,\end{cases} \] and the total number of valid painting orders is given by \[ \frac{n!}{k!}\times f(k) \pmod{10^9+7}. \] (Note that in any complete painting order, the white walls can be painted arbitrarily.)

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of walls. The second line contains \(n\) space‐separated integers \(a_1, a_2, \ldots, a_n\), where each \(a_i\) is either 0 or 1.

outputFormat

Output a single integer, the number of valid painting orders modulo \(10^9+7\).

sample

3
0 0 0

6