有一个长度为 $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$ 严格递增。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$