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

计算满足以下条件的排列 $p$（$p$ 为 $[1, 2, \dots, n]$ 的一个排列）的数量：对于所有满足 $l \le r \le m_l$ 的 $(l, r)$，子数组 $[p_l, p_{l+1}, \dots, p_r]$ 都不是 $[l, l+1, \dots, r]$ 的一个排列。

由于答案可能很大，你只需要求出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200$)，表示排列的长度。

第二行包含 $n$ 个整数 $m_1, m_2, \dots, m_n$ ($0 \le m_i \le n$)。

输出格式

输出满足条件的排列的数量，对 $10^9 + 7$ 取模。

样例

输入格式 1

3
1 2 3

输出格式 1

2

说明

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

输入格式 2

5
2 4 3 4 5

输出格式 2

38

输入格式 3

5
5 1 1 1 1

输出格式 3

0