Description

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$.

Input Format

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 Format

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

4				
5 12 35 5	

8

Hint

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