分数: 500 点
问题陈述
给定的是一个序列 A of N 数字。找出分离的方法数 A 进入一些非空连续子序列 B_1, B_2, \ldots, B_k 以满足以下条件:
- 对于每个 i\ (1 \leq i \leq k),中的元素之和 B_i 可以被整除 i.
由于计数可能很大,因此将其模数打印出来 (10^9+7).
约束
- 1 \leq N \leq 3000
- 1 \leq A_i \leq 10^{15}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印分隔序列以满足问题陈述中的条件的方法数,模数 (10^9+7).
示例输入 1
4 1 2 3 4
示例输出 1
3
我们有三种方法来分离序列,如下:
- (1),(2),(3),(4)
- (1,2,3),(4)
- (1,2,3,4)
示例输入 2
5 8 6 3 3 3
示例输出 2
5
示例输入 3
10 791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733
示例输出 3
15
输入中的值可能不适合 32- 位整数类型。