0715 - 数列の操作

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer snuke / x 7 / 統計 /


TLE
1sec
MLE
64MB
得点
100

問題文

長さ $N$ の整数列 $A$ が与えられます。

$1$ つ数を選んで消すという操作を $N$ 回繰り返して数列を空にすることを考えます。消した数よりも左にある数は $1$ ずつ減ります。まだ消されていない数が負になることがあってはなりません。

このとき、数を消す順番として考えられるものは何通りあるかを $mod\ 1,000,000,007$ で求めて下さい。

制約

  • $1 \leq N \leq 100$
  • $0 \leq A_i$
  • $A_i \leq A_{i+1}+1$ を満たす。
  • $A_N = 0$

入力

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

$N$
$A_1$ $A_2$ $...$ $A_N$

入力例 1

3
0 1 0

出力例 1

2

「$1,2,3$ の順に消す」、「$1,3,2$ の順に消す」の $2$ 通りがあります。

例えば後者の場合、数列は $\{0,1,0\}$ → $\{1,0\}$ → $\{0\}$ → $\{\}$ と変化します。

入力例 2

25
4 3 13 19 18 17 16 15 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1 0

出力例 2

948334170

$mod$ を取るのを忘れないようにして下さい。