AT_abc207_e [ABC207E] Mod i

题目描述

给定一个长度为 $N$ 的数列 $A$。请计算将 $A$ 切分为若干个连续且非空的子序列 $B_1,B_2,\ldots,B_k$ 的方案数，要求满足以下条件：

• 对于所有 $i\ (1 \leq i \leq k)$，$B_i$ 中所有元素的和能够被 $i$ 整除。

由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出满足题目条件的切分方案数，对 $10^9+7$ 取模。

样例 1

输入

4
1 2 3 4

输出

3

样例 2

输入

5
8 6 3 3 3

输出

5

样例 3

输入

10
791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733

输出

15

说明/提示

限制条件

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

样例解释 1

存在以下 $3$ 种切分方式：

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

样例解释 3

输入数据可能超出 $32$ 位整数的表示范围。

由 ChatGPT 4.1 翻译