Problem Background

Professor JOI is a historian studying the history of the Kingdom of IOI.

Problem Description

He has discovered the ruins of an ancient row of stone pillars and an ancient document.

The document describes the following:
- When first constructed, there were $2 \times N$ stone pillars, with two pillars of height $k$ for each $1 \le k \le N$. The height of the $i$-th pillar is denoted as $h_i$.
- There will be $N$ earthquakes, each reducing the height of some pillars by $1$ while leaving others unchanged.
- A pillar $i$ remains unchanged during an earthquake if and only if $h_i \ge 1$ and for all $j > i$, $h_i \neq h_j$.
- After $N$ earthquakes, exactly $N$ pillars remain.

Now, Professor JOI has identified the positions of the remaining $N$ pillars, $A_1, A_2, \ldots, A_N$. He wants you to determine the number of possible initial configurations of the heights of the $2 \times N$ pillars, modulo $10^9 + 7$.

Input Format

The first line contains an integer $N$.

The next line contains $N$ integers, representing $A_1, A_2, \ldots, A_N$.

Output Format

Output a single integer, the number of possible initial configurations of the heights of the $2 \times N$ pillars modulo $10^9 + 7$.

Sample Input and Output

Sample Input 1

3
3 4 6

Sample Output 1

5

Sample Input 2

1
1

Sample Output 2

0

Sample Input 3

10
5 8 9 13 15 16 17 18 19 20

Sample Output 3

147003663

Notes

Sample Explanation

Sample 1 Explanation

One possible solution is $(2, 2, 3, 3, 1, 1)$.
- After the first earthquake, it becomes $(1, 2, 2, 3, 0, 1)$.
- After the second earthquake, it becomes $(0, 1, 2, 3, 0, 1)$.
- After the third earthquake, it becomes $(0, 0, 2, 3, 0, 1)$.

Four other solutions are:
- $(2, 3, 2, 3, 1, 1)$.
- $(2, 3, 3, 2, 1, 1)$.
- $(3, 2, 2, 3, 1, 1)$.
- $(3, 2, 3, 2, 1, 1)$.

Sample 2 Explanation

For $N = 1$, there is only one construction plan $(1, 1)$. After one earthquake, it becomes $(0, 1)$, and it is impossible for the pillar at position $1$ to exist.

Sample 3 Explanation

There are $111147004440$ possible construction plans, and $111147004440 \bmod 10^9 + 7 = 147003663$.

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le N \le 600$, $1 \le A_i \le 2 \times N$, and $A_i < A_{i+1}$.

Notes

This problem is adapted from the 19th Japanese Olympiad in Informatics Spring Training Camp Day 2 T3 Ancient Ruins 3.

见题面 Input 部分

见题面 Output 部分