UOJ Logo Universal Online Judge

UOJ

#506. 【JOISC2020】遗迹

附件下载 统计

JOI 教授是 IOI 王国历史研究的权威专家。他在考察 IOI 王国一座古老的寺庙时发现了若干个石柱。他同时找到了 IOI 王国古人类关于石柱的说明书。说明如下:

  • 在寺庙刚建造完成时,恰好有 $2N$ 个石柱,编号为 $1$ 至 $2N$ 。对于每个 $1 \le i \le N$,恰好有两个高度为 $i$ 的石柱。石柱 $i$ 的初始高度为 $h_i$。
  • 随后发生了 $N$ 次地震,每次地震后,一些石柱被损坏,使得其高度减少1。高度为0的石柱高度不再减少。但是部分石柱被古人保护了下来,它们的高度没有发生变化。
  • 当地震发生时,对于每个 $1 \le i \le N$,恰好有一个高度为 $i$ 的石柱被保护下来。如果有多个高度为 $i$ 的石柱,则编号最大的被保护了下来。形式化的,石柱 $i$ 被保护当且仅当不存在 $i < j \le 2N$ ,使得 $h_i=h_j$。
  • 在 $N$ 次地震后,恰好有 $N$ 个石柱高度大于0。

JOI 教授觉得如果达能求出 $2N$ 个石柱的初始高度,他就搞出了大新闻。它发现在 $N$ 次地震后,剩余的石柱编号依次为 $A_1,A_2,\cdots,A_N$ 。JOI 教授想要知道有多少种合法的初始序列,使得其在发生 $N$ 次地震后,剩余的石柱坐标恰好为 $A_1,A_2,\cdots,A_N$。由于方案数很多,你只需要输出答案对 $1000000007(10^9+7)$ 取模的结果即可。

输入格式

第一行一个正整数 $N$ 。

第二行 $N$ 个正整数,第 $i$ 个正整数表示 $A_i$。

输出格式

一行一个整数表示答案,对 $1000000007(10^9+7)$ 取模。

样例一

input

3
3 4 6

output

5

explanation

设初始石柱高度序列为 $(2,2,3,3,1,1)$。因为对于每个$1 \le i \le 3$,恰有两个高度为 $i$ 的石柱,因此满足条件。

第一次地震结束后,石柱 $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

output

0

explanation

唯一初始石柱高度序列为 $(1,1)$。

第一次地震结束后,石柱 $2$ 被保护,高度变为 $(0,1)$。

因此剩余石柱编号为 $(2)$,不满足题意,答案为0。

样例三

10
5 8 9 13 15 16 17 18 19 20

output

147003663

explanation

总共有 $111147004440$ 种符合条件的初始高度组合,将这个数除 $10^9+7$ 余数为 $147003663$,即输出值。

数据范围

子任务1($6$分): $N \le 13$。

子任务2($52$分): $N \le 60$。

子任务3($42$分): 无特殊限制。

对于所有测试数据,满足$1 \le N \le 600,1 \le A_i \le 2N,A_i \le A_{i+1}(1 \le i < N)$。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$