P3213 [HNOI2011] Pythagorean Theorem

Momo has been studying the Pythagorean Theorem. For two positive integers $A$ and $B$, if there exists a positive integer $C$ such that $A^2 + B^2 = C^2$, and $A$ and $B$ are coprime, then $(A, B)$ is called a primitive Pythagorean pair. One day, Momo obtained $N$ sticks, each with a positive integer length. She plans to select some of these sticks to play a puzzle game. To make the pattern look artfully messy, she wants the lengths of any two selected sticks to not form a primitive Pythagorean pair. Now, Momo wants to know how many selection schemes meet the requirement. Since the answer may be large, you only need to output the result modulo $10^9 + 7$.

The first line contains a positive integer $N$, the number of sticks. The second line contains $N$ space-separated positive integers $h_1, h_2, \cdots, h_N$, where for $1 \le i \le N$, $h_i$ denotes the length of the $i$-th stick. The testdata guarantees that: - For $30\%$ of the testdata, for all $1 \le i \le N$, $1 \le h_i \le 3000$. - For another $30\%$ of the testdata, for all $1 \le i \le N$, $1 \le h_i \le 2 \times 10^5$. - For the remaining $40\%$ of the testdata, for all $1 \le i \le N$, $2 \times 10^4 \le h_i \le 10^6$. - For $100\%$ of the testdata, $N \le 10^6$.

Output a single non-negative integer, the number of valid selection schemes modulo $10^9 + 7$.

Sample explanation: $(5, 12)$ and $(12, 35)$ are primitive Pythagorean pairs, so there are $8$ valid selection schemes, namely: $\{5\}, \{12\}, \{35\}, \{5\}, \{5,35\}, \{35,5\}, \{5,5\}, \{5,35,5\}$. Translated by ChatGPT 5