Coprime Products from Six Indices

You are given $N$ integers $X_1, X_2, \dots, X_N$. For each ordered pair $(i, j)$, define $Y_{i,j} = X_i \times X_j \bmod 359999$.

Count the number of ordered 6-tuples $(a, b, c, d, e, f)$ that satisfy all of the following conditions.

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

Use $\gcd(0, 0) = 0$ in this definition.

The first line contains the integer $N$.

The second line contains $X_1, X_2, \dots, X_N$, separated by spaces.

Print the number of ordered 6-tuples satisfying the condition, modulo $10^9 + 7$.

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