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

题目描述

一开始，你有一个长为 $n$ 的序列 $a_1,a_2,a_3...a_n$。

你觉得它有些长了，所以决定将它按原来的顺序分割成若干连续的段，但分割时要保证第 $i$ 段中的数字之和是 $i$ 的倍数。

两个分割方案被视为不同当且仅当存在一个数字，在两个方案中属于不同的段。请你输出满足要求的分割方案数 $\mod 10^9+7$的值。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数表示序列的每一项。

输出格式

输出一个非负整数表示你的答案。

输入输出样例

样例输入 #1

4
1 2 3 4

样例输出 #1

3

样例解释 #1

合法的三种方案为：

1 | 2 | 3 | 4（第一段为1，第二段为2，第三段为3，第四段为4）

1 2 3 | 4（第一段为1 2 3 ，第二段为4）

1 2 3 4 （不做分割）

以下是不合法的分割方案

1 2 | 3 |4（第二段和为3，不是2的倍数）

1 3 |2 4 （调换了位置，不合法）

样例输入 #2

5
8 6 3 3 3

样例输出 #2

5

数据范围与约定

对于 $20\%$ 的数据，保证 $1\leq n \leq 20$

对于 $50\%$ 的数据，保证 $1\leq n \leq 500$

对于 $100\%$ 的数据，保证 $1\leq n \leq 3000$，$1\leq a_i \leq 10^{15}$。