题目描述

小蓝是一名勤劳的粉刷匠，今天他收到了一份来自蓝桥学院的委托，需要为学院的 $n$ 面墙进行粉刷。这 $n$ 面墙从左到右依次排列，编号从 $1$ 到 $n$。起初，所有墙的颜色均为白色。

学院希望小蓝能将其中一部分墙刷成蓝色，以营造一种冷色调的艺术氛围。为此，学院给小蓝提供了一个长度为 $n$ 的数组 $\{a_1, a_2, \cdots, a_n\}$，来指定每面墙的颜色要求。具体地，如果 $a_i = 0$，则第 $i$ 面墙保持白色；如果 $a_i = 1$，则小蓝需要将第 $i$ 面墙刷成蓝色。

小蓝每次只能刷一面墙，他会将一面墙完整的刷完后再刷另一面墙。为了确保整体墙面的视觉效果，学院还提一个小小的要求：在粉刷过程中，如果要将第 $i$ 面墙刷成蓝色，那么它右侧（第 $i + 1$ 面墙 $\sim$ 第 $n$ 面墙）蓝色的墙的个数必须是偶数（包括 $0$ 个）。

现在，请你计算小蓝共有多少种刷墙顺序可以满足学院的要求？由于答案可能很大，因此你只需要给出答案对 $10^9 + 7$ 取模后的结果即可。

在本题中，不同的刷墙方法只与小蓝刷墙的顺序有关。例如，先刷第 $1$ 面墙再刷第 $2$ 面墙，与先刷第 $2$ 面墙再刷第 $1$ 面墙，被视为两种不同的方法。

输入格式

输入的第一行包含一个正整数 $n$，表示墙的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔，按编号从 $1$ 到 $n$ 的顺序依次表示每面墙的颜色要求。

输出格式

输出一行包含一个整数，表示满足要求的刷墙顺序数量对 $10^9 + 7$ 取模后的结果。

4
1 1 1 1

4

2
0 0

1

提示

样例说明

在样例 $1$ 中，有 $4$ 面墙，且都需要刷为蓝色。总共有以下 $4$ 种粉刷顺序可以满足学院的要求：

1. $[1,2,3,4]$：先刷第 $1$ 面，再刷第 $2$ 面，然后刷第 $3$ 面，最后刷第 $4$ 面。
2. $[1,3,4,2]$：先刷第 $1$ 面，再刷第 $3$ 面，然后刷第 $4$ 面，最后刷第 $2$ 面。
3. $[2,3,1,4]$：先刷第 $2$ 面，再刷第 $3$ 面，然后刷第 $1$ 面，最后刷第 $4$ 面。
4. $[3,4,1,2]$：先刷第 $3$ 面，再刷第 $4$ 面，然后刷第 $1$ 面，最后刷第 $2$ 面。

在样例 2 中，有 $2$ 面墙，且都要保持白色。只有 $1$ 种刷墙方法可以满足学院的要求，即不刷任何一面墙壁。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 13$，$a_i = 1$。
• 对于所有评测用例，$1 \leq n \leq 2 \times 10^5$，$0 \leq a_i \leq 1$。