1335번 - 여섯 쌍 서로소

문제

$N$개의 정수 $X_1, X_2, \dots X_N$가 있다. $Y_{i,j} = X_i \times X_j \bmod {359999}$ 이다.

다음 조건을 만족하는 $(a, b, c, d, e, f)$의 개수를 구해보자.

• 1ドル \le a, b, c, d, e, f \le N$
• $gcd(Y_{a,b}, Y_{c,d}, Y_{e,f}) = 1$

$gcd(0, 0) = 0$이다.

입력

첫째 줄에 $N,ドル 둘째 줄에 $X_1, X_2, \dots X_N$이 주어진다.

출력

문제 조건을 만족하는 $(a, b, c, d, e, f)$의 개수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.

제한

• 1ドル \le N \le 10^6$
• 1ドル \le X_j \le 10^6$

노트