题目背景

JOI 教授是一名研究 IOI 王国的历史学家。

题目描述

他发现了一行古代石柱的废墟及一份古代文献。

古代文献上的记载如下：

• 刚建造完成的时候，有 $2\times N$ 个石柱，对于 $1\le k\le N$ 均有两个石柱高度为 $k$，同时记第 $i$ 个石柱的高度为 $h_i$。
• 会发生 $N$ 次地震，每次地震会使一些石柱的高度 $-1$，其他石柱高度不变。
• 石柱 $i$ 地震时高度不变，当且仅当 $h_i\ge 1$ 并且对于 $j>i$ 都要有 $h_i\not=h_j$
• $N$ 次地震后，恰好只剩下了 $N$ 个石柱。

现在 JOI 教授找出了仅存的 $N$ 个石柱的位置 $A_1,A_2,\ldots,A_N$，他想让你求出，最初 $2\times N$ 个石柱高度的修建方案数 $\bmod~10^9+7$ 的值。

输入格式

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

接下来一行 $N$ 个数，表示 $A_1,A_2,\ldots,A_N$。

输出格式

仅一行一个整数，表示最初 $2\times N$ 个石柱高度的建造方案数 $\bmod~10^9+7$ 的值。

3
3 4 6

5

1
1

0

10
5 8 9 13 15 16 17 18 19 20

147003663

提示

样例解释

样例 1 解释

一种可行的解为 $(2,2,3,3,1,1)$。

• 第一次地震后，变为 $(1,2,2,3,0,1)$。
• 第二次地震后，变为 $(0,1,2,3,0,1)$。
• 第三次地震后，变为 $(0,0,2,3,0,1)$。

另外四种解如下：

• $(2,3,2,3,1,1)$。
• $(2,3,3,2,1,1)$。
• $(3,2,2,3,1,1)$.
• $(3,2,3,2,1,1)$。

样例 2 解释

对于 $N=1$ 的情况，显然只有 $(1,1)$ 一种修建方案，在一次地震后，会变为 $(0,1)$，$1$ 号位置不可能有石柱。

样例 3 解释

共有 $111147004440$ 种可能的修建方案，$111147004440 \bmod 10^9+7=147003663$。

子任务

对于 $100\%$ 的数据，保证 $1\le N\le 600$，$1\le A_i\le 2\times N$，$A_i< A_{i+1}$。 | Subtask 编号 | $N\le$ | 分数 | | :-: |:-: | :-: | | $1$ | $13$ | $6$ | $2$| $60$ | $52$ | $3$ | 无 | $42$

说明

本题译自 第 19 回日本情報オリンピック　春季トレーニング合宿 Day 2 T3 最古の遺跡 3。