Given an array of $n$ integers, count the number of subsets whose elements' product is a square number.

Also count the empty subset with product equal to one.

The first line has an integer $n$ : the size of the array.

The next line has $n$ integers $x_1, x_2,\dots, x_n$ : the contents of the array.

• $1 \le n \le 5000$
• $1 \le x_i \le 5000$

Print one integer: the answer to the problem modulo $10^9 + 7$ .