没加 LaTeX 是这样的捏。

---

题目描述

沫沫最近在研究勾股定理。对于两个正整数 $A$ 与 $B$，若存在正整数 $C$ 使得 $A^2+B^2=C^2$，且 $A$ 与 $B$ 互质，则称 $(A,B)$ 为一个互质勾股数对。

有一天，沫沫得到了 $N$ 根木棍，其长度都是正整数，她准备从中挑选出若干根木棍来玩拼图游戏，为了使拼出的图案有凌乱美，她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在，沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大，你只要输出答案对 $10^9+7$ 取模的结果。

输入格式

输入文件第一行是一个正整数 $N$，表示共有多少根木棍。

输入文件第二行是用空格隔开的 $N$ 个正整数 $h_1, h_2, \dots, h_N$，其中对 $1 \le i \le N$，$h_i$ 表示第 $i$ 根木棍的长度。

输入的数据保证 $30\%$ 的数据满足对 $1 \le i \le N$ 有 $1 \le h_i \le 3000$，

另外 $30\%$ 的数据满足对 $1 \le i \le N$ 有 $1 \le h_i \le 200000$，

剩下的 $40\%$ 的数据满足对 $1 \le i \le N$ 有 $20000 \le h_i \le 1000000$，

$100\%$ 的数据满足 $N≤1000000$。

输出格式

输出仅包含一个非负整数，表示满足要求的挑选木棍的方案数对 $10^9+7$ 取模的结果。

提示

样例解释：$(5,12)$ 与 $(12,35)$ 是互质勾股数对，故满足要求的挑选木棍的方案有 $8$ 种，即：

$\{5\},\{12\},\{35\},\{5\},\{5,35\},\{35,5\},\{5,5\},\{5,35,5\}$。

---

## 题目描述

沫沫最近在研究勾股定理。对于两个正整数 $A$ 与 $B$，若存在正整数 $C$ 使得 $A^2+B^2=C^2$，且 $A$ 与 $B$ 互质，则称 $(A,B)$ 为一个互质勾股数对。

有一天，沫沫得到了 $N$ 根木棍，其长度都是正整数，她准备从中挑选出若干根木棍来玩拼图游戏，为了使拼出的图案有凌乱美，她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在，沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大，你只要输出答案对 $10^9+7$ 取模的结果。

## 输入格式

输入文件第一行是一个正整数 $N$，表示共有多少根木棍。

输入文件第二行是用空格隔开的 $N$ 个正整数 $h_1, h_2, \dots, h_N$，其中对 $1 \le i \le N$，$h_i$ 表示第 $i$ 根木棍的长度。

输入的数据保证 $30\%$ 的数据满足对 $1 \le i \le N$ 有 $1 \le h_i \le 3000$，

另外 $30\%$ 的数据满足对 $1 \le i \le N$ 有 $1 \le h_i \le 200000$，

剩下的 $40\%$ 的数据满足对 $1 \le i \le N$ 有 $20000 \le h_i \le 1000000$，

$100\%$ 的数据满足 $N≤1000000$。

## 输出格式

输出仅包含一个非负整数，表示满足要求的挑选木棍的方案数对 $10^9+7$ 取模的结果。

## 提示

样例解释：$(5,12)$ 与 $(12,35)$ 是互质勾股数对，故满足要求的挑选木棍的方案有 $8$ 种，即：

$\{5\},\{12\},\{35\},\{5\},\{5,35\},\{35,5\},\{5,5\},\{5,35,5\}$。