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

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

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

第一行一个正整数n。

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

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

样例解释 #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  （调换了位置，不合法）

数据范围

- 对于 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}。