首先我们可以处理出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:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
const
d39 =;
var
n :longint;
pre, other :array[..] of longint;
last :array[..] of longint;
l :longint;
c, cur :array[..] of longint;
pi :array[..] of longint;
ans :int64;
tot, sum :longint;
flag :array[..] of boolean;
b :array[..,..] of longint;
w :array[..,..] of int64;
function gcd(a,b:longint):longint;
begin
if b>a then exit(gcd(b,a)) else
if b= 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:= to do
for j:= to do
if gcd(*i-,*j)= then
begin
x:=(*i-)*(*i-)+(*i-)*(*j);
y:=*j*j+(*i-)*(*j);
if (x<=) and (y<=) then
begin
connect(x,y);
connect(y,x);
end;
end;
end;
procedure init;
var
i :longint;
x :longint;
begin
read(n);
for i:= to n do
begin
read(x);
inc(c[x]);
end;
pi[]:=;
for i:= to n do pi[i]:=pi[i-]* mod d39;
ans:=;
end;
procedure dfs(x,fa:longint);
var
q, r, p :longint;
f :boolean;
begin
flag[x]:=true;
q:=last[x];
r:=;
while q<> do
begin
p:=other[q];
f:=true;
if c[p]> 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,]:=x;
b[tot,]:=p;
end;
if r<> 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,]:=; w[x,]:=pi[c[x]]-;
if cur[x]= then w[x,]:=;
if cur[x]= then w[x,]:=;
while q<> do
begin
p:=other[q];
if (c[p]>) and (p<>fa) then
begin
dp(p,x);
w[x,]:=w[x,]*(w[p,]+w[p,]) mod d39;
w[x,]:=w[x,]*w[p,] 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,);
sum:=(sum+w[num,]) mod d39;
sum:=(sum+w[num,]) mod d39;
exit;
end;
x:=b[p,]; y:=b[p,];
curx:=cur[x]; cury:=cur[y];
if (curx<>) and (cury<>) then
begin
cur[x]:=;
cur[y]:=;
dfs_q(p+,num);
cur[x]:=curx;
cur[y]:=cury;
end;
if (curx<>) then
begin
cur[x]:=;
dfs_q(p+,num);
cur[x]:=curx;
cur[y]:=cury;
end;
end;
procedure main;
var
i :longint;
begin
for i:= to do
if (c[i]>) and (not flag[i]) then
begin
tot:=;
sum:=;
dfs(i,);
dfs_q(,i);
ans:=ans*sum mod d39;
end;
if ans= then ans:=d39;
writeln(ans-);
end;
begin
make;
init;
main;
end.