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