有 $N$ 个人正在睡觉，编号为 $1$ 到 $N$。Snuke 想要用 $N-1$ 根绳子将他们连接起来！
- 每根绳子的两端必须连接两个不同的人。这两个人将被一根绳子直接连接。
- 所有人必须通过绳子直接或间接地连接在一起。
- 第 $i$ 个人必须连接恰好 $a_i$ 根绳子。
计算满足上述所有条件的连接方案数，结果对 $10^9+7$ 取模。如果两种方案中存在一对人，在其中一种方案中被绳子直接连接，而在另一种方案中没有，则认为这两种方案不同。
输入格式
第一行包含一个整数 $N$ ($2 \le N \le 10^5$)。接下来的 $N$ 行中，第 $i$ 行包含一个整数 $a_i$，表示第 $i$ 个人必须连接的绳子数量 ($1 \le a_i \le 3$)。
输出格式
在一行中输出答案。
样例
样例输入 1
9 1 3 2 1 3 1 2 1 2
样例输出 1
1260