P7213 [JOISC 2020] 最古の遺跡 3

JOI 教授是一名研究 IOI 王国的历史学家。

他发现了一行古代石柱的废墟及一份古代文献。 古代文献上的记载如下： - 刚建造完成的时候，有 $2\times N$ 个石柱，对于 $1\le k\le N$ 均有两个石柱高度为 $k$，同时记第 $i$ 个石柱的高度为 $h_i$。 - 会发生 $N$ 次地震，每次地震会使一些石柱的高度 $-1$，其他石柱高度不变。 - 石柱 $i$ 地震时高度不变，当且仅当 $h_i\ge 1$ 并且对于 $j>i$ 都要有 $h_i\not=h_j$ - $N$ 次地震后，恰好只剩下了 $N$ 个石柱。 现在 JOI 教授找出了仅存的 $N$ 个石柱的位置 $A_1,A_2,\ldots,A_N$，他想让你求出，最初 $2\times N$ 个石柱高度的修建方案数 $\bmod~10^9+7$ 的值。

第一行为一个整数 $N$。 接下来一行 $N$ 个数，表示 $A_1,A_2,\ldots,A_N$。

仅一行一个整数，表示最初 $2\times N$ 个石柱高度的建造方案数 $\bmod~10^9+7$ 的值。

#### 样例解释 #### 样例 1 解释 一种可行的解为 $(2,2,3,3,1,1)$。 - 第一次地震后，变为 $(1,2,2,3,0,1)$。 - 第二次地震后，变为 $(0,1,2,3,0,1)$。 - 第三次地震后，变为 $(0,0,2,3,0,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)$。 #### 样例 2 解释 对于 $N=1$ 的情况，显然只有 $(1,1)$ 一种修建方案，在一次地震后，会变为 $(0,1)$，$1$ 号位置不可能有石柱。 #### 样例 3 解释 共有 $111147004440$ 种可能的修建方案，$111147004440 \bmod 10^9+7=147003663$。 #### 子任务 对于 $100\%$ 的数据，保证 $1\le N\le 600$，$1\le A_i\le 2\times N$，$A_i< A_{i+1}$。 | Subtask 编号 | $N\le$ | 分数 | | :-: |:-: | :-: | | $1$ | $13$ | $6$ | $2$| $60$ | $52$ | $3$ | 无 | $42$ #### 说明 本题译自 [第 19 回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) Day 2 [T3 最古の遺跡 3](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day2/ruins3-en.pdf)。