← 返回题目列表

Codeforces · 316/D3

D3. 体育课

中文机器翻译题面 查看原题

聪明海狸决定不仅要聪明,还要做一只健康的海狸!于是他开始在X学校上体育课。在这所学校,体育课有一位非常有创意的老师。他最喜欢的热身运动之一是扔球。学生们排队。一开始每个人都会得到一个球。球的编号从 1 到 n(根据库存委员会的要求)。

图 1.n = 5 时的初始位置。

收到球后,学生进行热身练习。该练习通过几次投掷进行。每次投掷,老师都会选择任意两个不同的学生来参加。被选中的学生互相扔球。因此,每次投掷后,学生们都保持在自己的位置上,并且交换两个球。

图 2. 投掷示例。

在这种情况下,持有第 2 个球和第 4 个球的学生之间发生了投掷。由于热身有很多练习,每项只能持续很少的时间。因此,对于每个学生,我们知道他可以参加的最大投掷次数。对于本课程,最大投掷次数为 1 或 2 次。

请注意,在所考虑的练习的所有阶段之后,任何球都可能落在任何学生身上。 Smart Beaver 决定将其形式化并引入“球顺序”的概念。球顺序是由 n 个数字组成的序列,与该行中球的顺序相对应。第一个数字将与该行左边第一个学生的球的号码相匹配,第二个数字将与第二个学生的球相匹配,依此类推。例如,在图 2 中,球的顺序是 (1, 2, 3, 4, 5),投掷后是 (1, 4, 3, 2, 5)。聪明的海狸知道学生的数量,并且对于每个学生,他知道他可以参加的最大投掷次数。现在他想知道:到练习结束时,有多少种不同的球顺序方式。

输入

第一行包含一个数字 n — 队列中学生的数量和球的数量。下一行恰好包含 n 个空格分隔的整数。每个数字对应该行中的一名学生(第 i 个数字对应该行中从左边算起的第 i 个学生),并显示他可以参加的投掷次数。

得分 30 分的输入限制为(子问题 D1):

- 1 ≤ n ≤ 10。

得分 70 分的输入限制为(子问题 D1+D2):

- 1 ≤ n ≤ 500。

获得 100 分的输入限制为(子问题 D1+D2+D3):

- 1 ≤ n ≤ 1000000。

输出

输出应包含一个整数 - 热身练习完成后球顺序的变体数量。由于数字可能相当大,因此将其打印为对 1000000007 (109 + 7) 取模。

示例

输入 #1

5
1 2 2 1 2

输出 #1

120

输入 #2

8
1 2 2 1 2 1 1 2

输出 #2

16800