Divisible Subarrays

2 secs 1024 MB
sepa38's icon sepa38

問題文

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

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

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

制約

  • 1N10001 \leq N \leq 1000
  • 1Ai1091 \leq A_i \leq 10 ^ 9

入力

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

NA1    A2       ⁣...    ANN\\ A_1 \;\; A_2 \;\;\;\! ... \;\; A_N\\

出力

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

サンプル

入力1
3
1 5 3
出力1
4

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

入力2
5
1 2 3 4 5
出力2
5

Submit


Go (1.21)