题目描述

题目译自 JOISC 2020 Day2 T3「最古の遺跡 3 / Ruins 3」

JOI 教授是 IOI 国有名的历史学家。他在研究 IOI 国一个古庙时发现了石柱的遗迹以及一篇古 IOI 国人写的文档。 在文档中，给出了这些石柱的相关描述，具体如下：

• 刚建好时，庙里有 $2N$ 根石柱，编号为 $1\ldots 2N$。对于任意 $k\in [1,N]$，恰好有两根石柱的高度为 $k$。
• 随后发生了 $N$ 次地震，损坏了某些石柱，每次损坏将使石柱的高度减一。由于古人类的保护，其他石柱未被损坏，高度保持不变。
• 地震发生时，对于任意 $k\in [1,N]$，古人类将保护恰好一根高度为 $k$ 的石柱。如果有多根石柱高度相同，根据古人类达成的共识，他们将选择保护编号最大的那一根。也就是说，如果石柱 $i$ 在地震前高度是 $h_i$，古人类会去选择保护这根石柱当且仅当 $h_i\ge 1$ 且任意 $j>i$ 满足 $h_j\neq h_i$。
• $N$ 次地震后，只剩下 $N$ 根石柱了，即只有 $N$ 根石柱的高度至少为 $1$。

JOI 教授觉得如果他能还原出来这些石柱地震前的高度，他能搞个大新闻。在他更仔细的研究后，发现 $N$ 次地震后留下来的石柱的编号为 $A_1,A_2,\ldots,A_N$。他想知道原来的高度组合有多少种可能。因为你是 JOI 教授的学徒（pupil），他想让你写个程序计算这个方案数。

你的任务是编写一个程序，给出 $N$ 次地震后留下来的石柱的编号，计算初始时 $2N$ 根石柱的高度组合种数模 $10^9+7$。

输入格式

第一行一个整数 $N$。

接下来一行 $N$ 个空格分隔的整数 $A_1,\ldots,A_n$。

输出格式

输出题面描述中所求的方案数模 $10^9+7$ 的值。

3
3 4 6

5

1
1

0

10
5 8 9 13 15 16 17 18 19 20

147003663

数据范围与提示

对于 $100\%$ 的数据，有 $1\le N\le 600,~$$1\le A_i\le 2N(1\le i\le N),~$$A_i<A_{i+1}(1\le i\le N-1)$。

各子任务详情如下：