여섯 인덱스의 서로소 곱

$N$개의 정수 $X_1, X_2, \dots, X_N$가 주어진다. 각 순서쌍 $(i, j)$에 대해 $Y_{i,j} = X_i \times X_j \bmod 359999$로 정의한다.

다음 조건을 모두 만족하는 순서 있는 6-튜플 $(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$이 공백으로 구분되어 주어진다.

조건을 만족하는 순서 있는 6-튜플의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

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