该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

第1行：$1$个正整数$n$； 第2行：$n$个正整数$a[i]$。 其中$n\leq3000，a[i]\leq10^{15}$。

输出格式

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

数据范围

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

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

输入样例

4
1 2 3 4

输出样例

3

样例解释

有这样的3种分法：

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

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

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