Problem ID:
fourcoprime
Points:
3.5 (partial)
Time limit:
2.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Perl, Python
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
Comments