CF316D1.PE Lesson

Smart Beaver decided to be not only smart, but also a healthy beaver! And so he began to attend physical education classes at school X. In this school, physical education has a very creative teacher. One of his favorite warm-up exercises is throwing balls. Students line up. Each one gets a single ball in the beginning. The balls are numbered from 1 to n (by the demand of the inventory commission).

Figure 1. The initial position for n = 5.

After receiving the balls the students perform the warm-up exercise. The exercise takes place in a few throws. For each throw the teacher chooses any two arbitrary different students who will participate in it. The selected students throw their balls to each other. Thus, after each throw the students remain in their positions, and the two balls are swapped.

Figure 2. The example of a throw.

In this case there was a throw between the students, who were holding the 2-nd and the 4-th balls. Since the warm-up has many exercises, each of them can only continue for little time. Therefore, for each student we know the maximum number of throws he can participate in. For this lessons maximum number of throws will be 1 or 2.

Note that after all phases of the considered exercise any ball can end up with any student. Smart Beaver decided to formalize it and introduced the concept of the "ball order". The ball order is a sequence of n numbers that correspond to the order of balls in the line. The first number will match the number of the ball of the first from the left student in the line, the second number will match the ball of the second student, and so on. For example, in figure 2 the order of the balls was (1, 2, 3, 4, 5), and after the throw it was (1, 4, 3, 2, 5). Smart beaver knows the number of students and for each student he knows the maximum number of throws in which he can participate. And now he is wondering: what is the number of distinct ways of ball orders by the end of the exercise.

聪明的海狸决定不仅要聪明，还要成为一名健康的海狸！因此，他开始在学校 X 参加体育课。该校的体育老师极具创造力，而他最钟爱的热身练习之一便是抛球游戏。学生们排成一列，每人初始时获得一个球。这些球按库存管理委员会的要求编号为 $1$ 到 $n$。

图 1. $n = 5$ 时的初始状态。

学生拿到球后便开始进行热身练习。该练习由若干次抛球动作组成。每次抛球时，老师任选两名不同的学生参与；这两名学生将各自手中的球相互抛给对方。因此，每次抛球后，学生位置保持不变，但这两个球的位置发生交换。

图 2. 一次抛球的示例。

本例中，持有第 2 号球和第 4 号球的学生进行了抛球。由于热身项目繁多，每项练习持续时间都很短。因此，对每位学生而言，我们已知其最多可参与的抛球次数；本节课中，每位学生的最大参与次数为 $1$ 或 $2$。

注意：经过该练习的所有阶段后，任意一个球都可能最终落在任意一名学生手中。聪明的海狸为此进行了形式化定义，并引入了“球序”（ball order）的概念。球序是一个长度为 $n$ 的数字序列，表示队列中球的排列顺序：序列第一个数对应从左起第一位学生所持球的编号，第二个数对应第二位学生所持球的编号，依此类推。例如，图 2 中初始球序为 $(1, 2, 3, 4, 5)$，抛球后变为 $(1, 4, 3, 2, 5)$。聪明的海狸已知学生人数 $n$，以及每位学生最多可参与的抛球次数。现在他想知道：练习结束时，可能产生的不同球序共有多少种？

The first line contains a single number n — the number of students in the line and the number of balls. The next line contains exactly n space-separated integers. Each number corresponds to a student in the line (the i-th number corresponds to the i-th from the left student in the line) and shows the number of throws he can participate in.

The input limits for scoring 30 points are (subproblem D1):

• 1 ≤ n ≤ 10.

The input limits for scoring 70 points are (subproblems D1+D2):

• 1 ≤ n ≤ 500.

The input limits for scoring 100 points are (subproblems D1+D2+D3):

• 1 ≤ n ≤ 1000000.

第一行包含一个整数 $n$ —— 表示队列中的学生人数，也等于球的数量。
下一行包含恰好 $n$ 个以空格分隔的整数。每个整数对应队列中的一个学生（第 $i$ 个数对应从左往右数第 $i$ 个学生），表示该学生最多能参与的传球次数。

得分为 30 分的输入限制（子问题 D1）：

• $1 \leq n \leq 10$。

得分为 70 分的输入限制（子问题 D1+D2）：

• $1 \leq n \leq 500$。

得分为 100 分的输入限制（子问题 D1+D2+D3）：

• $1 \leq n \leq 1000000$。

The output should contain a single integer — the number of variants of ball orders after the warm up exercise is complete. As the number can be rather large, print it modulo 1000000007 (109 + 7).

输出应为一个整数——热身练习完成后小球排列方式的种数。由于该数可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。