P7213 [JOISC 2020] The Oldest Ruins 3

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

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$.

The first line contains an integer $N$. The next line contains $N$ numbers, representing $A_1,A_2,\ldots,A_N$.

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

#### 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}$. | Subtask ID | $N\le$ | Score | | :-: |:-: | :-: | | $1$ | $13$ | $6$ | | $2$ | $60$ | $52$ | | $3$ | None | $42$ | #### Notes This problem is translated from Day 2 [T3 The Oldest Ruins 3](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day2/ruins3-en.pdf) of [The 19th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html). Translated by ChatGPT 5