有一个长度为 $2n$ 的高度序列 $h$，其中 $1 \sim n$ 每个数都恰好出现了 $2$ 次。
之后进行了若干次操作，每次操作会让满足存在 $i < j, h_i=h_j$ 的 $i$ 的 $h$ 减一。如果 $h$ 为 $0$ 则不再下降。
当进行了足够多次操作后，我们可以证明，会有恰好 $n$ 个位置的 $h$ 不为 $0$，且他们的值恰好为 $1 \sim n$ 各一次。
现在给定你这 $n$ 个位置 $p_1,p_2,\cdots,p_n$，你需要求出满足这样的条件的 $h$ 的个数模 $10^9+7$ 的值。
输入格式
第一行，一个整数 $n$。
第二行，$n$ 个整数 $p_i$。
输出格式
一行，一个整数，表示答案。
样例一
input
3 3 4 6
output
5
explanation
$(2,2,3,3,1,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)$ 满足条件。因此答案为 $5$。
样例二
input
10 5 8 9 13 15 16 17 18 19 20
output
147003663
数据范围与提示
对于所有数据，$1\le n\le 500$，$1 \leq p_i \leq 2n$，$p_i$ 严格递增。
| 子任务编号 | $n\le $ | 分值 |
|---|---|---|
| $1$ | $6$ | $20$ |
| $2$ | $20$ | $20$ |
| $3$ | $50$ | $30$ |
| $4$ | $ $ | $30$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$