Mo is currently 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 coprime Pythagorean pair.

One day, Mo obtained $N$ wooden sticks, each with a positive integer length. She plans to select a subset of these sticks to play a puzzle game. To ensure the resulting pattern has a "chaotic beauty," she wants to select a subset such that no two sticks in the selection form a coprime Pythagorean pair. Now, Mo wants to know how many such valid selection schemes exist. Since the answer can be very large, you only need to output the result modulo $10^9 + 7$.

Input

The first line contains a positive integer $N$, representing the total number of wooden sticks. The second line contains $N$ space-separated positive integers $h_1, h_2, \dots, h_N$, where $h_i$ represents the length of the $i$-th stick for $1 \le i \le N$.

The input data is guaranteed to satisfy: 30% of the data satisfies $1 \le h_i \le 3000$ for all $1 \le i \le N$. Another 30% of the data satisfies $1 \le h_i \le 200000$ for all $1 \le i \le N$. The remaining 40% of the data satisfies $20000 \le h_i \le 1000000$ for all $1 \le i \le N$. 100% of the data satisfies $N \le 1000000$.

Output

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

Examples

Input 1

4
5 12 35 5

Output 1

8

Note

$(5, 12)$ and $(12, 35)$ are coprime Pythagorean pairs. Therefore, there are 8 valid selection schemes: $\{5\}$, $\{12\}$, $\{35\}$, $\{5\}$, $\{5, 35\}$, $\{35, 5\}$, $\{5, 5\}$, $\{5, 35, 5\}$.