여섯 인덱스의 서로소 곱

시간 제한2초메모리 제한512 MB

요약

N개의 정수가 주어질 때, 359999(=599*601)로 나눈 세 쌍의 곱의 최대공약수가 1이 되는 순서쌍 6개의 개수를 1e9+7로 나눈 나머지로 구하는 문제입니다.

문제

$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)$ 의 개수를 구하자.

정의에 따라 $\gcd(0, 0) = 0$ 으로 둔다.

첫째 줄에 정수 $N$ 이 주어진다.

둘째 줄에 $X_1, X_2, \dots, X_N$ 이 공백으로 구분되어 주어진다.

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