問題文
長さ $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$ を取るのを忘れないようにして下さい。