题目大意：给你一个序列，你可以在序列中任选一个子序列，求子序列每一项的积是一个平方数的方案数。
1<=a[i]<=70
因为任何一个大于2的数都可以表示成几个质数的幂的乘积
所以我们预处理70以内的质数，把它作为二进制状压的状态，每个在序列中出现数Hash一下，组合数推一下
所以把奇次幂的状态表示为1，偶次幂的状态就是0，比如6就是11，42就是1011
而平方数的每个质因子的指数都是偶数，所以最终结果的状态就是0000000...
转移的过程，两个数的乘积，就是这两个数的质因子二进制的状态的合并，即异或(xor)运算
卡常很恶心，懒得进一步优化了
好吧据说可以推出结论，这个组合数加起来其实是2的幂次
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 100100
#define M 75
#define mod 1000000007
#define C(m,n) (((fac[n]*inv[m])%mod*inv[n-m])%mod)
#define ll long long
using namespace std; int xx,n,now,lst;
int hx[M];
ll x,y,t;
ll inv[N],fac[N],f[][(<<)+];
int pr[]={,,,,,,,,,,,,,,,,,,};
int gc()
{
int rett=,fh=;char c=getchar();
while(c<''||c>'') {if(c=='-')fh=-; c=getchar();}
while(c>=''&&c<='') {rett=rett*+c-'';c=getchar();}
return rett*fh;
}
void exgcd(ll a,ll b)
{
if(b==) {x=,y=;}
else {exgcd(b,a%b);t=x;x=y;y=t-a/b*y;}
}
void get_inv()
{
inv[]=inv[]=,fac[]=fac[]=;
for(ll i=;i<=n;i++)
{
exgcd(i,mod);
fac[i]=(fac[i-]*i)%mod;
x=(x%mod+mod)%mod;
inv[i]=(inv[i-]*x)%mod;
}
} int main()
{
//freopen("aa.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++) xx=gc(),hx[xx]++;
get_inv();
now=,lst=,f[][]=;
for(int i=;i<=;i++)
{
if(!hx[i]) continue;
int s=,x=i;
for(int j=;j<;j++)
{
while(x%pr[j]==)
{
s^=(<<j);
x/=pr[j];
}
}
for(int p=;p<(<<);p++)
{
if(!f[lst][p]) continue;
for(int j=;j<=hx[i];j++)
{
if(j&)
{
f[now][p^s]+=(f[lst][p]*C(j,hx[i]))%mod;
f[now][p^s]%=mod;
}else{
f[now][p]+=(f[lst][p]*C(j,hx[i]))%mod;
f[now][p]%=mod;
}
}
f[lst][p]=;
}
swap(now,lst);
}
printf("%I64d\n",f[lst][]-);
return ;
}