Cho dãy số nguyên ~A~ độ dài ~N~, đếm số bộ ~(i, j, k, z)~ sao cho ~1 \leq i < j < k < z \leq N~ và ~\text{UCLN}(A_i, A_j, A_k, A_z) = 1~.

Input

Gồm nhiều bộ test, mỗi bộ test có dạng:

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 10^6)~ - độ dài của dãy số ~A~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(1 \leq A_i \leq 10^6)~ - các phần tử của dãy số.

Output

In ra số bộ số thỏa mãn điều kiện đề bài theo modulo ~10^9+7~.

Scoring

• Subtask 1 ~(20\%)~: ~1 \leq N \leq 50~.
• Subtask 2 ~(30\%)~: Mọi phần tử ~A_i~ đều là lũy thừa của ~2~.
• Subtask 3 ~(50\%)~: Không có ràng buộc gì thêm.

Sample Input

4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8

Sample Output

1
0
34