JOI 王国的教授是 IOI 王国历史研究的顶尖专家。当他在 IOI 王国的一座古庙进行考察时，他发现了建造石柱的遗迹。他还发现了一份据说是 IOI 王国古人所写的古文献。文献中包含了关于石柱的描述。更确切地说，文献中写着以下内容：

• 刚建造完成时，共有 $2N$ 根石柱，编号从 $1$ 到 $2N$。
• 刚建造完成时，对于每个 $k$ ($1 \le k \le N$)，恰好有两根高度为 $k$ 的石柱。
• 地震发生了 $N$ 次。每次地震后，一些石柱会倒塌，它们的高度会减少 $1$。然而，另一些石柱被古人保护了起来。这些石柱没有倒塌，它们的高度保持不变。
• 当发生地震时，对于每个 $k$ ($1 \le k \le N$)，恰好有一根高度为 $k$ 的石柱被古人保护。如果地震发生时有超过一根高度为 $k$ 的石柱，则编号最大的高度为 $k$ 的石柱会被保护。换句话说，如果地震前石柱 $i$ ($1 \le i \le 2N$) 的高度为 $h_i$，那么石柱 $i$ 被保护当且仅当 $h_i \ge 1$ 且对于所有 $j > i$ 都有 $h_j \neq h_i$。
• $N$ 次地震发生后，剩下 $N$ 根石柱（即恰好有 $N$ 根高度至少为 $1$ 的石柱）。

JOI 教授认为，如果能恢复 $2N$ 根石柱建造时的高度，那将是一个伟大的发现。他更详细地考察了石柱建造的地方。他发现，在 $N$ 次地震发生后，剩余石柱的编号为 $A_1, A_2, \dots, A_N$。

JOI 教授想知道 $2N$ 根石柱在建造时高度的可能组合数。作为 JOI 教授的学生，请你编写一个程序来计算这个数量。

编写一个程序，给定 $N$ 次地震后剩余石柱的编号，计算 $2N$ 根石柱在建造时高度的可能组合数，结果对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据。输入中的所有值均为整数。

$N$ $A_1 \dots A_N$

输出格式

将结果输出到标准输出。输出答案除以 $1\,000\,000\,007$ 的余数。

数据范围

• $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 分) 无附加限制。

样例

样例输入 1

3
3 4 6

样例输出 1

5

样例输入 2

1
1

样例输出 2

0

样例输入 3

10
5 8 9 13 15 16 17 18 19 20

样例输出 3

147003663