問題文

一列に並んだ $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$ で割った余りを出力せよ。

---

入力例 1

3
3 2 1

出力例 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$ 個です。

---

入力例 2

3
1 1 2

出力例 2

1

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

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

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

---

入力例 3

5
2 2 2 2 2

出力例 3

16

---

入力例 4

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

出力例 4

31155