There is a sequence of heights $h$ of length $2n$, where each number from $1$ to $n$ appears exactly twice.

A series of operations is performed. In each operation, for every $i$ such that there exists $j > i$ with $h_i = h_j$, the value of $h_i$ is decreased by $1$. If $h_i$ is $0$, it does not decrease further.

It can be proven that after a sufficient number of operations, there will be exactly $n$ positions where $h$ is non-zero, and their values will be exactly $1, 2, \dots, n$, each appearing once.

Given these $n$ positions $p_1, p_2, \dots, p_n$, find the number of such sequences $h$ that satisfy the condition, modulo $10^9+7$.

Input

The first line contains an integer $n$.

The second line contains $n$ integers $p_i$.

Output

A single integer representing the answer.

Examples

Input 1

3
3 4 6

Output 1

5

Note 1

The sequences $(2,2,3,3,1,1), (2,3,2,3,1,1), (2,3,3,2,1,1), (3,2,2,3,1,1), (3,2,3,2,1,1)$ satisfy the condition. Thus, the answer is $5$.

Input 2

10
5 8 9 13 15 16 17 18 19 20

Output 2

147003663

Constraints

For all test cases, $1 \le n \le 500$, $1 \le p_i \le 2n$, and $p_i$ are strictly increasing.