首先我们可以处理出10^6以内的所有的勾股数，如果我们有2*i-1和2*j互质，
那么A=(2*i-1)*(2*i-1)+(2*i-1)*(2*j)，B=2*j*j+(2*i-1)*(2*j)为互质
勾股数对，且保证所有的互质勾股数对都有这个性质，保证了了我们暴力可以枚举
所有的勾股数对
那么我们得到所有的勾股数对后，可以建图，得到一张类似于树的图，然后可能会有
一些环，但是比较少，一棵树的独立集个数是可以DP求的，那么这样的图可以暴力
规定每条非树边的两个端点取不取来每次都DP，得出所有情况，这样就行了。
/************************************************************** Problem: 2327 User: BLADEVIL Language: Pascal Result: Accepted Time:3372 ms Memory:67608 kb ****************************************************************/ //By BLADEVIL const d39 =1000000007; var n :longint; pre, other :array[0..2000010] of longint; last :array[0..1000010] of longint; l :longint; c, cur :array[0..1000010] of longint; pi :array[0..1000010] of longint; ans :int64; tot, sum :longint; flag :array[0..1000010] of boolean; b :array[0..1000010,0..2] of longint; w :array[0..1000010,0..2] of int64; function gcd(a,b:longint):longint; begin if b>a then exit(gcd(b,a)) else if b=0 then exit(a) else exit(gcd(b,a mod b)); end; procedure connect(x,y:longint); begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; end; procedure make; var i, j :longint; x, y :longint; begin for i:=1 to 1000 do for j:=1 to 1000 do if gcd(2*i-1,2*j)=1 then begin x:=(2*i-1)*(2*i-1)+(2*i-1)*(2*j); y:=2*j*j+(2*i-1)*(2*j); if (x<=1000000) and (y<=1000000) then begin connect(x,y); connect(y,x); end; end; end; procedure init; var i :longint; x :longint; begin read(n); for i:=1 to n do begin read(x); inc(c[x]); end; pi[0]:=1; for i:=1 to n do pi[i]:=pi[i-1]*2 mod d39; ans:=1; end; procedure dfs(x,fa:longint); var q, r, p :longint; f :boolean; begin flag[x]:=true; q:=last[x]; r:=0; while q<>0 do begin p:=other[q]; f:=true; if c[p]>0 then begin if not flag[p] then dfs(p,x) else if p<>fa then begin if x<p then begin inc(tot); b[tot,1]:=x; b[tot,2]:=p; end; if r<>0 then pre[r]:=pre[q] else last[x]:=pre[q]; f:=false; end; end; if f then r:=q; q:=pre[q]; end; end; procedure dp(x,fa:longint); var q, p :longint; begin q:=last[x]; w[x,0]:=1; w[x,1]:=pi[c[x]]-1; if cur[x]=1 then w[x,1]:=0; if cur[x]=2 then w[x,0]:=0; while q<>0 do begin p:=other[q]; if (c[p]>0) and (p<>fa) then begin dp(p,x); w[x,0]:=w[x,0]*(w[p,1]+w[p,0]) mod d39; w[x,1]:=w[x,1]*w[p,0] mod d39; end; q:=pre[q]; end; end; procedure dfs_q(p,num:longint); var x, y, curx, cury :longint; begin if p>tot then begin dp(num,0); sum:=(sum+w[num,0]) mod d39; sum:=(sum+w[num,1]) mod d39; exit; end; x:=b[p,1]; y:=b[p,2]; curx:=cur[x]; cury:=cur[y]; if (curx<>1) and (cury<>2) then begin cur[x]:=2; cur[y]:=1; dfs_q(p+1,num); cur[x]:=curx; cur[y]:=cury; end; if (curx<>2) then begin cur[x]:=1; dfs_q(p+1,num); cur[x]:=curx; cur[y]:=cury; end; end; procedure main; var i :longint; begin for i:=1 to 1000000 do if (c[i]>0) and (not flag[i]) then begin tot:=0; sum:=0; dfs(i,0); dfs_q(1,i); ans:=ans*sum mod d39; end; if ans=0 then ans:=d39; writeln(ans-1); end; begin make; init; main; end.