Public Judge

pjudge

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

# 21620. 【ExPR #1】下降

统计

有一个长度为 $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}$