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}$