CF316D3 PE Lesson

聪明的海狸决定不仅要聪明，还要做一个健康的海狸！于是他开始在 X 学校参加体育课。在这所学校里，体育老师非常有创意。他最喜欢的热身运动之一就是投球。学生们排成一排。每个人一开始都会得到一个球。球的编号从 $1$ 到 $n$（这是库存委员会的要求）。  图 1. $n=5$ 时的初始状态。拿到球后，学生们开始进行热身运动。这个运动会进行若干次投掷。每次投掷时，老师会任意选择两名不同的学生参与。他们互相把手中的球扔给对方。这样，每次投掷后，学生们仍然站在原地，只是两人的球交换了。  图 2. 一次投掷的示例。这次是持有第 $2$ 个球和第 $4$ 个球的学生进行了投掷。由于热身运动有很多环节，每个环节的时间都很短。因此，每个学生最多只能参与有限次数的投掷。对于本次课程，每个学生最多参与 $1$ 次或 $2$ 次投掷。 注意，在所有投掷结束后，任何一个球都可能在任何一个学生手中。聪明的海狸决定对这个过程进行形式化，并引入了“球序列”的概念。球序列是一个长度为 $n$ 的数列，表示球在队伍中的顺序。第一个数字表示最左边学生手中的球的编号，第二个数字表示第二个学生手中的球的编号，依此类推。例如，在图 $2$ 中，球的顺序原本是 $(1,2,3,4,5)$，投掷后变成了 $(1,4,3,2,5)$。聪明的海狸知道学生人数以及每个学生最多能参与多少次投掷。现在他想知道：在热身运动结束后，球序列可能有多少种不同的排列方式。

第一行包含一个整数 $n$，表示队伍中的学生数，也是球的数量。下一行包含 $n$ 个用空格分隔的整数。每个数字对应队伍中第 $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$。

输出一个整数，表示热身运动结束后球序列的不同排列方式的数量。由于答案可能很大，请输出对 $1000000007$（$10^9+7$）取模后的结果。

由 ChatGPT 4.1 翻译