模 i 划分

题目描述

给定由 $N$ 个数组成的数列 $A$。求将 $A$ 分割成若干个非空连续子序列 $B_1, B_2, \ldots, B_k$ 的方式数，使其满足以下条件：

对于每个 $i\ (1 \le i \le k)$，$B_i$ 中元素之和能被 $i$ 整除。

由于结果可能十分巨大，请输出对 $(10^9+7)$ 取模后的值。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出满足题目条件的分割方式数对 $(10^9+7)$ 取模后的值。

样例

4
1 2 3 4

3

共有以下 $3$ 种分割方式：

$(1),(2),(3),(4)$

$(1,2,3),(4)$

$(1,2,3,4)$

5
8 6 3 3 3

5

10
791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733

15

数据范围

• $1 \le N \le 3000$
• $1 \le A_i \le 10^{15}$
• 输入均为整数

提示

输入中的数值可能超出 32 位整数类型。