题目限制

1000ms 256M

题目描述

一开始，你有一个长为$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

样例输入 #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}$。