[R40E]Yet another counting problem - 代码源竞赛平台

时空限制

1s/512M

题目描述

给定两个大小均为 $n$ 的点集 $A$ 和 $B$，集合中的点编号均为 $1$ 到 $n$。

这两个集合之间的连边规则如下： 对于集合 $B$ 中的第 $i$ 个点 $B_i$，它只能与集合 $A$ 中编号在前 $a_i$ 个的点（即 $A_1, A_2, \dots, A_{a_i}$）建立连接。

我们需要在 $A$ 和 $B$ 之间选择若干条边组成一个匹配，要求 $A$ 和 $B$ 中的每个点最多只能被一条边连接。

在此基础上，我们定义一个匹配是极大匹配，当且仅当它满足以下条件：

1. 该匹配本身是合法的。
2. 无法再从剩余未匹配的点中找到一对 $(B_i, A_j)$，使得它们之间存在连边规则允许的边。

换句话说，对于任意一个未被匹配的 $B_i$，它所有能连接的 $A$ 类节点（$A_1 \dots A_{a_i}$）都必须已经被匹配。

请统计有多少种不同的极大匹配方案。由于答案可能很大，请输出结果对 $10^9 + 7$ 取模后的值。

格式

输入格式

第一行包含一个正整数 $n$，表示集合的大小。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示点 $B_i$ 可以连接的 $A$ 类点的范围是 $[1, a_i]$。

输出格式

输出一个整数，表示极大匹配的方案数对 $10^9 + 7$ 取模的结果。

样例

样例输入 #1

3
3 1 1

样例输出 #1

5

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$
$1$	$10$	$8$
$2$	$40$	$400$
$3$	$50$	$3000$

对于 $100\%$ 的数据，$1 \le n \le 3000$，$0 \le a_i \le n$。