Primitive Pythagorean Pairs


Do you know the Pythagorean theorem? Definitely yes. Do you know Pythagorean triples? Maybe not. Do you know primitive Pythagorean pairs? Definitely not, because Bruce has not defined it yet! Let's start from Pythagorean triples. A Pythagorean triple consists of three positive integers a, b and c, such that a2 + b2 = c2. If a and b are also coprime, the pair (a,b) is named a primitive Pythagorean pair, like (3, 4). Bruce will tell you how to generate primitive Pythagorean pairs. Given two positive integers m and n (m > n), if m and n are coprime and m - n is odd, a primitive Pythagorean pair (a,b) can be calculated by a = m2 - n2 and b = 2·m·n. There are an infinite number of primitive Pythagorean pairs.

Now Bruce has N cards, such of which has a positive integer vi (i = 1,2,...,N). He wants to pick up a number of cards so that there are no primitive Pythagorean pairs among the selected cards. Could you please help Bruce to get the total number of different selections? Two selections are different if and only if one card is in one selection, but is not in the other selection. Bruce has to select at least one card in each selection.


The first line of input will consist of one integer, N (1 ≤ N ≤ 1 000 000), the number of cards Bruce has. The second line of input will consist of N positive integers v1, v2,...,vn, where vi (1 ≤ vi ≤ 200 000 or 20 000 ≤ vi ≤ 1 000 000 for all i=1..n) is the value of card i (1 ≤ i ≤ N).


Output one integer, the number of different selections modulo 109 + 7.

Example input:
5 12 35 5
Example output:

There are two primitive Pythagorean pairs (5,12) and (12,35). So there are 8 different selections: {5}, {12}, {35}, {5}, {5,35}, {35,5}, {5,5}, {5, 35, 5}.

Time and memory limit:

  • 2s
  • 256MB

Problem source: DMOJ