给定一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$。考虑某个长度为 $n$ 且由 $1$ 到 $n$ 之间的整数组成的数组（允许元素相等）。我们按以下方式对数组进行变换：首先，取出数组中所有等于 $p_1$ 的元素并写在纸上（如果没有这样的元素，则什么都不写）。接着写下所有等于 $p_2$ 的元素，然后是等于 $p_3$ 的元素，以此类推，最后写下所有等于 $p_n$ 的元素，从而得到一个长度为 $n$ 的新数组。例如，如果排列为 $2\ 1\ 3$，数组为 $2\ 3\ 2$，则变换后的数组为 $2\ 2\ 3$。如果变换后得到的数组是有序的，我们称原数组为“关于 $p$ 可排序的”。计算关于 $p$ 可排序的数组的总数。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2000$)：排列的长度。第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)：排列本身。

输出格式

输出一个整数：答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

2
2 1

样例输出 1

2

样例输入 2

3
2 1 3

样例输出 2

15