← 返回题目列表

Codeforces · 1874/F

F. 水母和 OEIS

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

Jellyfish总是使用OEIS来解决数学问题,但现在她发现了一个OEIS无法解决的问题:

计算 $$$[1, 2, \dots, n]$$$ 的排列 $$$p$$$ 的数量,使得对于所有 $$$(l, r)$$$ 且 $$$l \leq r \leq m_l$$$,子数组 $$$[p_l, p_{l+1}, \dots, p_r]$$$ 不是以下的排列$$$[l,l+1,\点,r]$$$。

由于答案可能很大,您只需对 $$$10^9+7$$$ 求模即可。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 200$$$) — 排列的长度。

输入的第二行包含 $$$n$$$ 整数 $$$m_1, m_2, \dots, m_n$$$ ($$$0 \leq m_i \leq n$$$)。

输出

输出满足条件的不同排列的数量,以 $$$10^9+7$$$ 为模。

示例

输入 #1

3
1 2 3

输出 #1

2

输入 #2

5
2 4 3 4 5

输出 #2

38

输入 #3

5
5 1 1 1 1

输出 #3

0

注意

在第一个示例中,$$$[2, 3, 1]$$$ 和 $$$[3, 1, 2]$$$ 满足条件。