Background

Special for beginners, ^_^

Description

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

Format

Input

从文件input.txt中读入数据，输入文件第一行是一个正整数N，表示共有多少根木棍。输入文件第二行是用空格隔开的N个正整数hi， ha，…， hs， 其中对1≤i≤N， h表示第i根木棍的长度。输入的数据保证30%的数据满足对1≤i≤N有1≤hi≤3000，另外30%的数据满足对1≤i≤N有1≤h≤200000，剩下的40%的数据满足对1≤i≤N有20000≤h≤1000000，100%的数据满足N≤1000000。

Output

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

Samples

4
512355

8

Limitation

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