配点 : $1000$ 点

問題文

一列に並んだ $N$ 棟のビルが建設中であり、ビルには左から順番に $1, 2, \ldots, N$ の番号がついています。

長さ $N$ の整数列 $X$ が与えられ、ビル $i$ の高さ $H_i$ は、$1$ 以上 $X_i$ 以下の整数のいずれかにすることができます。

$1 \leq i \leq N$ に対して、$P_i$ を次のように定めます。

• $H_j > H_i$ を満たすような整数 $j (1 \leq j < i)$ が存在する場合はそのような $j$ の最大値、存在しない場合は $-1$ とする

全てのビルの高さの組み合わせを考えるとき、 $P$ としてありうる整数列の個数を $1000000007$ で割った余りを求めてください。

制約

• $1 \leq N \leq 100$
• $1 \leq X_i \leq 10^5$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$X_1$ $X_2$ $\cdots$ $X_N$

出力

全てのビルの高さの組み合わせを考えるとき、 $P$ としてありうる整数列の個数を $1000000007$ で割った余りを出力せよ。

3
3 2 1

4

$H$ としては、次の $6$ 通りが考えられます。

• $H = (1, 1, 1)$ のとき、$P$ は $(-1, -1, -1)$ である
• $H = (1, 2, 1)$ のとき、$P$ は $(-1, -1, 2)$ である
• $H = (2, 1, 1)$ のとき、$P$ は $(-1, 1, 1)$ である
• $H = (2, 2, 1)$ のとき、$P$ は $(-1, -1, 2)$ である
• $H = (3, 1, 1)$ のとき、$P$ は $(-1, 1, 1)$ である
• $H = (3, 2, 1)$ のとき、$P$ は $(-1, 1, 2)$ である

よって、$P$ としてありうる整数列は $(-1, -1, -1), (-1, -1, 2), (-1, 1, 1), (-1, 1, 2)$ の $4$ 個です。

3
1 1 2

1

$H$ としては、次の $2$ 通りが考えられます。

• $H = (1, 1, 1)$ のとき、$P$ は $(-1, -1, -1)$ である
• $H = (1, 1, 2)$ のとき、$P$ は $(-1, -1, -1)$ である

よって、$P$ としてありうる整数列は $1$ 個です。

5
2 2 2 2 2

16

13
3 1 4 1 5 9 2 6 5 3 5 8 9

31155