Description

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

The ancient document states the following:

• When it was just completed, there were $2\times N$ stone pillars. For each $1\le k\le N$, there were exactly two pillars of height $k$. Let the height of the $i$-th pillar be $h_i$.
• There will be $N$ earthquakes. Each earthquake decreases the height of some pillars by $-1$, while the heights of the other pillars remain unchanged.
• During an earthquake, the height of pillar $i$ does not change if and only if $h_i\ge 1$ and for all $j>i$, we have $h_i\not=h_j$.
• After $N$ earthquakes, exactly $N$ pillars remain.

Now Professor JOI has found the positions $A_1,A_2,\ldots,A_N$ of the remaining $N$ pillars. He wants you to compute the number of possible initial construction plans for 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$ numbers, representing $A_1,A_2,\ldots,A_N$.

Output Format

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

3
3 4 6

5

1
1

0

10
5 8 9 13 15 16 17 18 19 20

147003663

Hint

Sample Explanation

Sample 1 Explanation

One feasible 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)$.

The other four 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 the case $N=1$, clearly there is only one construction plan: $(1,1)$. After one earthquake, it becomes $(0,1)$, so it is impossible for there to be a pillar at position $1$.

Sample 3 Explanation

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

Subtasks

For $100\%$ of the testdata, 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 translated from Day 2 T3 The Oldest Ruins 3 of The 19th Japanese Olympiad in Informatics Spring Training Camp.

Translated by ChatGPT 5