pro：给定N个数Xi(Xi<1e18)，保证每个数的素因子小于2e3；问有多少种方案，选处一些数，使得数的乘积是完全平方数。求答案%1e9+7； N<300;
sol：小于2e3的素数只有304个。选或者不选看成1和0，那么问题其实就是问%2意义下的*元。 答案是2^*元
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int Mod=1e9+;
int a[][],vis[maxn],p[],tot;
void prime()
{
for(int i=;i<maxn;i++){
if(!vis[i]) p[tot++]=i;
for(int j=;j<=tot&&p[j-]*i<maxn;j++){
vis[i*p[j-]]=;
if(i%p[j-]==) break;
}
}
}
int Gauss(int N,int M)
{
int free=;
for(int i=,p=;i<N&&p<M;i++,p++){
int t=i;
rep(j,i+,N-) if(a[j][p]>a[t][p]) t=j;
if(!a[t][p]){ i--; free++; continue;}
if(i!=t) rep(j,p,M) swap(a[i][j],a[t][j]);
rep(j,i+,N-){
if(!a[j][p]) continue;
rep(k,p,M) a[j][k]^=a[i][k];
}
}
return free;
}
int main()
{
prime();
int T,N,num,C=; ll x;
scanf("%d",&T);
while(T--){
memset(a,,sizeof(a));
scanf("%d",&N);
rep(i,,N-) {
scanf("%lld",&x);
rep(j,,tot-){
ll tx=x;
while(tx%p[j]==){
tx/=p[j]; a[j][i]^=;
}
}
}
int t=Gauss(tot,N);
int res=;
rep(i,,t) res=res*%Mod;
printf("Case #%d:\n%d\n",++C,(res+Mod-)%Mod);
}
return ;
}