#3193. 划分数组

划分数组

题目限制

1500 ms 256 M

题目描述

给出一个包含 nn 个元素的数组 aa ,数组元素为 a[1]a[1]a[n]a[n] ,我们将数组 aa 划分为若干段,要求:

ii 段的数字之和,是 ii 的倍数,求有多少种可行的划分方案,由于结果很大,输出对 109+710^9+7 取模的结果即可。

输入格式

11 行: 11 个数 nn ; 第 22 行: nn 个数 a[i]a[i] 。 其中 n3000n\le 3000a[i]1e15a[i]\le 1e15

输出格式

输出方案数量对 109+710^9+7 取模的结果。

数据范围

对于 26%26\% 的数据, 1n101 \le n \le 10

对于 100%100\% 的数据, 1n3000,1a[i]10151 \le n \le 3000, 1 \le a[i] \le 10^{15}

输入样例 1

4
1 2 3 4

输出样例 1

3