#3276. 「JOISC 2020 Day2」遗迹

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

题目译自 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

样例输出 1

5

样例解释 1

假设初始时石柱的高度为 (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 种高度组合符合输入数据和题面描述的条件。

样例输入 2

1
1

样例输出 2

0

样例解释 2

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

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

样例输入 3

10
5 8 9 13 15 16 17 18 19 20

样例输出 3

147003663

样例解释 3

总共有 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)

各子任务详情如下:

子任务编号 分值 特殊限制
1 6 N\le 13
2 52 N\le 60
3 42 无特殊限制