问题陈述

给定一个包含 $N$ 个数字的序列 $A$。找到将 $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$ 位整数类型。