Cho một mảng gồm ~n~ số nguyên, hãy đếm số tập con sao cho tích các phần tử là một số chính phương.

Cũng tính cả tập con rỗng với tích bằng một.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên ~n~: kích thước của mảng.

Dòng tiếp theo chứa ~n~ số nguyên ~x\_1, x\_2,\dots, x\_n~: nội dung của mảng.

Kết quả

In ra một số nguyên: kết quả của bài toán modulo ~10^9 + 7~.

Giới hạn

• ~1 \le n \le 5000~
• ~1 \le x\_i \le 5000~

Ví dụ

Dữ liệu vào:

4
2 2 3 6

Kết quả:

4