题目限制

1500 ms 256 M

题目描述

给出一个包含 $n$ 个元素的数组 $a$ ，数组元素为 $a[1]$ 到 $a[n]$ ，我们将数组 $a$ 划分为若干段，要求：

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

输入格式

第 $1$ 行： $1$ 个数 $n$ ； 第 $2$ 行： $n$ 个数 $a[i]$ 。 其中 $n\le 3000$ ， $a[i]\le 1e15$ 。

输出格式

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

数据范围

对于 $26\%$ 的数据， $1 \le n \le 10$ ；

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

输入样例 1

4
1 2 3 4

输出样例 1

3