Dado un arreglo de ~n~ enteros, cuente el número de subconjuntos cuyos elementos suman un cuadrado perfecto.

Cuente también el subconjunto vacío cuyo producto sea igual a uno.

Entrada

La primera línea contiene un entero ~n~: el tamaño del arreglo. La siguiente línea contiene n enteros ~x_1, x_2,\dots, x_n~: los elementos del arreglo.

Salida

Imprima un entero: la solución al problema módulo ~10^9 + 7~.

Restricciones

• ~1 \leq n \leq 5000~
• ~1 \leq x_i \leq 5000~

Ejemplo de Entrada

4
2 2 3 6

Ejemplo de Salida

4