Square Subsets.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Dado un arreglo de $n$ ~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$ ~n~: el tamaño del arreglo. La siguiente línea contiene n enteros $x_1, x_2,\dots, x_n$ ~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$ ~10^9 + 7~.

Restricciones

$1 \leq n \leq 5000$ ~1 \leq n \leq 5000~
$1 \leq x_i \leq 5000$ ~1 \leq x_i \leq 5000~

Ejemplo de Entrada

4
2 2 3 6

Ejemplo de Salida

Comments

There are no comments at the moment.