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]$$$ 满足条件。