Non-coprime Pythagorean Pair-Free Subset

MoMo is 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 \(\gcd(A,B)=1\), then the pair \((A,B)\) is called a coprime Pythagorean pair.

One day, MoMo got N wooden sticks, each with a positive integer length. She wants to select a subset of these sticks to form a puzzle. In order to create a touch of chaotic beauty in the pattern, she requires that for any two selected sticks, their lengths do not form a coprime Pythagorean pair. In other words, for any two selected sticks with lengths \(a\) and \(b\) (with \(a\ne b\)), it must not be that there exists a positive integer \(c\) satisfying \[ a^2 + b^2 = c^2, \] and \(\gcd(a,b)=1\).

Your task is to count the number of subsets (possibly empty) of the wooden sticks that satisfy the above condition. Since the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains an integer \(N\), the number of wooden sticks.

The second line contains \(N\) positive integers, representing the lengths of the wooden sticks.

outputFormat

Output a single integer: the number of valid selections modulo \(10^9+7\).

sample

3
3 4 5

6