Cho một dãy các số nguyên dương $chẵn$ $a_1,a_2,\ldots,a_n$. Đếm số tập hợp $S$ $\subset$ {$1;2;\ldots;n$} sao cho $a_{S_1}\times a_{S_2}\times \ldots \times a_{S_{\left| S \right|}}$ là một $số$ $hoàn$ $hảo$.

Input

• Dòng đầu tiên gồm số nguyên dương $n$ $(n \le 10^6)$.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ $(a_i \le 2 \times 10^{18})$.

Output

• Ghi số lượng tập $S$ thỏa mãn. Vì số lượng tập $S$ có thể rất lớn nên chỉ cần in số tập sau khi chia lấy dư cho $10^9+7$.

Constraints

• $20$% số điểm có $n \le 10$ và $a_i \le 10$.
• $20$% số điểm khác có $n \le 10$ và $a_i \le 18$.
• $20$% số điểm khác có $n \le 20$.
• $20$% số điểm khác có $n \le 1000$.
• $20$% số điểm còn lại không có giới hạn gì thêm.

Example

Sample input

4 
2 2 14 6

3

Note

Có $3$ cách chọn sau:

• $a_1 \times a_3 = 2 \times 14 = 28$
• $a_2 \times a_3 = 2 \times 14 = 28$
• $a_4 = 6$