310712: CF1874F. Jellyfish and OEIS

F. Jellyfish and OEIStime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Jellyfish always uses OEIS to solve math problems, but now she finds a problem that cannot be solved by OEIS:

Count the number of permutations $p$ of $[1, 2, \dots, n]$ such that for all $(l, r)$ such that $l \leq r \leq m_l$, the subarray $[p_l, p_{l+1}, \dots, p_r]$ is not a permutation of $[l, l+1, \dots, r]$.

Since the answer may be large, you only need to find the answer modulo $10^9+7$.

Input

The first line of the input contains a single integer $n$ ($1 \leq n \leq 200$) — the length of the permutation.

The second line of the input contains $n$ integers $m_1, m_2, \dots, m_n$ ($0 \leq m_i \leq n$).

Output

Output the number of different permutations that satisfy the conditions, modulo $10^9+7$.

ExamplesInput

3
1 2 3

Output

2

Input

5
2 4 3 4 5

Output

38

Input

5
5 1 1 1 1

Output

0

Note

In the first example, $[2, 3, 1]$ and $[3, 1, 2]$ satisfies the condition.

题目大意：
计算满足特定条件的排列数量。给定一个长度为n的排列p，对于所有满足l ≤ r ≤ m_l的(l, r)，数组[p_l, p_{l+1}, …, p_r]不是数组[l, l+1, …, r]的排列。输出满足条件的不同排列数量，结果对10^9+7取模。

输入数据格式：
第一行：一个整数n（1 ≤ n ≤ 200）——排列的长度。
第二行：n个整数m_1, m_2, …, m_n（0 ≤ m_i ≤ n）。

输出数据格式：
满足条件的不同排列的数量，对10^9+7取模。

示例：
输入：
3
1 2 3
输出：
2

输入：
5
2 4 3 4 5
输出：
38

输入：
5
5 1 1 1 1
输出：
0题目大意： 计算满足特定条件的排列数量。给定一个长度为n的排列p，对于所有满足l ≤ r ≤ m_l的(l, r)，数组[p_l, p_{l+1}, …, p_r]不是数组[l, l+1, …, r]的排列。输出满足条件的不同排列数量，结果对10^9+7取模。 输入数据格式： 第一行：一个整数n（1 ≤ n ≤ 200）——排列的长度。 第二行：n个整数m_1, m_2, …, m_n（0 ≤ m_i ≤ n）。 输出数据格式： 满足条件的不同排列的数量，对10^9+7取模。 示例： 输入： 3 1 2 3 输出： 2 输入： 5 2 4 3 4 5 输出： 38 输入： 5 5 1 1 1 1 输出： 0