题目描述

题目译自 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$ 的值。

样例 1

3
3 4 6

5

假设初始时石柱的高度为 $(2,2,3,3,1,1)$。因为对于 $k\in[1,3]$ 的各个高度都恰好有 $2$ 根石柱，因此符合题面描述中的条件。

• 第一次地震时，石柱 $2,4,6$ 被古人类保护。地震后，石柱高度变为 $(1,2,2,3,0,1)$。
• 第二次地震时，石柱 $3,4,6$ 被古人类保护。地震后，石柱高度变为 $(0,1,2,3,0,1)$。
• 第三次地震时，石柱 $3,4,6$ 被古人类保护。地震后，石柱高度变为 $(0,0,2,3,0,1)$。 三次地震后，石柱 $3,4,6$ 留下来了，与输入一致。

除了这个例子，可能的高度组合还有 $(2,3,2,3,1,1),~$$(2,3,3,2,1,1),~$$(3,2,2,3,1,1),~$$(3,2,3,2,1,1)$。

因此，总共有 $5$ 种高度组合符合输入数据和题面描述的条件。

1
1

0

本输入的唯一可能高度组合为 $(1,1)$。地震后，石柱高度变为 $(0,1)$。

因此，没有符合输入数据和题面描述给出的条件的初始高度组合。

10
5 8 9 13 15 16 17 18 19 20

147003663

总共有 $111~147~004~440$ 种符合条件的初始高度组合，将这个数除 $10^9+7$ 余数为 $147~003~663$，即输出值。

数据范围与提示

对于 $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)$。

各子任务详情如下：