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ử của chúng là một số chính phương.

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

Đầ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\): các phần tử của mảng.

Đầu ra

In ra một số nguyên: đáp án của bài toán modulo \(10^9 + 7\).

Constraints

• \(1 \le n \le 5000\)

• \(1 \le x_i \le 5000\)

Example

4
2 2 3 6

4