問題文

長さ $N$ の配列 $A$ が与えられます。 $A$ をいくつかの連続した空でない部分列 $B_1, B_2, ..., B_k$ に切り分けることを考えます。 このとき、以下の条件を満たす切り分け方が何通りあるか求めてください。

• $i$ $(1 \leq i \leq k)$ について、$B_i$ に含まれる要素の和は $|B_i|$ で割り切れる。

ただし、答えは非常に大きくなる可能性があるので、$10 ^ 9 + 7$ で割った余りを出力してください。

制約

• $1 \leq N \leq 1000$
• $1 \leq A_i \leq 10 ^ 9$

入力

入力は以下の形式で与えられます。

出力

計算結果を一行に出力せよ。

サンプル

3
1 5 3

4

$(1 \ | \ 3 \ | \ 5), (1 \ | \ 3, 5), (1, 3 \ | \ 5), (1, 3, 5)$ すべての切り分け方が条件を満たします。

5
1 2 3 4 5

5