Cho một dãy gồm \(n\) số nguyên dương, các số có giá trị không vượt quá 30

Hãy lập trình xác định số tập con của \(n\) phần tử đã cho sao cho tích các phần tử có trong mỗi tập hợp không chia hết cho bất kỳ số chính phương lớn hơn \(1\) nào.

Input

• Dòng thứ nhất: Một số nguyên dương \(n \le 10^4\)
• Dòng thứ hai: ghi \(n\) số nguyên dương.

Output

• Một số là phần dư của kết quả tìm được khi chia cho \(10^9+7\)

Example

Sample input

5
2 2 3 4 6

Sample output

6