Dada una secuencia ~A~ de ~N~ números. Encuentre la cantidad de maneras de separar ~A~ en algún número de subsecuencias contiguas no vacías ~B_1, B_2,...,B_k~ tal que se cumpla la siguiente condición:

• Para cada ~i~ ~(1 \leq i \leq k)~, la suma de los elementos en ~B_i~ es divisible por ~i~.

Ya que dicha cantidad puede ser enorme, exprésela módulo ~(10^9 + 7)~.

Constantes

• ~(1 \leq n \leq 3000)~
• ~(1 \leq A_i \leq 10^{15})~
• Todos los valores de la entrada son enteros

Entrada

La entrada se dará en el siguiente formato:

• ~N~

• ~A_1~ ~A_2~ ~...~ ~A_N~

Salida

Imprima la cantidad de formas de separar la secuencia de tal manera que se cumpla la condición antes descrita, módulo ~(10^9 + 7)~.

Ejemplo #1 de Entrada

4
1 2 3 4

Ejemplo #1 de Salida

3

Tenemos tres maneras de separar la secuencia:

• ~(1),(2),(3),(4)~

• ~(1,2,3),(4)~

• ~(1,2,3,4)~

Ejemplo #2 de Entrada

5
8 6 3 3 3

Ejemplo #2 de Salida

5

Ejemplo #3 de Entrada

10
791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733

Ejemplo #3 de Salida

15

Puede que los valores de la entrada no entren en un entero de ~32~-bit.