← 返回题目列表

AtCoder · abc207_e

E. 模组我

中文机器翻译题面 查看原题

分数: 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- 位整数类型。