题目连接：https://vjudge.net/contest/392610#problem/B
解题思路：
对于每个质因子，显然只有偶数和奇数的两种情况需要考虑，考虑构建异或方程组。高斯消元法一个板子下来，求出自由未知元的个数，然后就是对自由元赋值，0或者1，总共有2^k种，别忘了去掉全是0的情况，因此答案是2^k -1

代码：

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MAXN 2010
#define N 2010
#define INF 0x3f3f3f3f
typedef long long ll;


int a[N][N];//增广矩阵
int x[N];//解集
int freeX[N];//自由变元
int Gauss(int equ,int var){//返回自由变元个数
    /*初始化*/
    for(int i=0;i<=var;i++){
        x[i]=0;
        freeX[i]=0;
    }

    /*转换为阶梯阵*/
    int col=0;//当前处理的列
    int num=0;//自由变元的序号
    int row;//当前处理的行
    for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
        int maxRow=row;//当前列绝对值最大的行
        for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
            if(abs(a[i][col])>abs(a[maxRow][col]))
                maxRow=i;
        }
        if(maxRow!=row){//与第row行交换
            for(int j=row;j<var+1;j++)
                swap(a[row][j],a[maxRow][j]);
        }
        if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
            freeX[num++]=col;//记录自由变元
            row--;
            continue;
        }

        for(int i=row+1;i<equ;i++){
            if(a[i][col]!=0){
                for(int j=col;j<var+1;j++){//对于下面出现该列中有1的行，需要把1消掉
                    a[i][j]^=a[row][j];
                }
            }
        }
    }

    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for(int i=row;i<equ;i++)
        if(a[i][col]!=0)
            return -1;

    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    int temp=var-row;//自由变元有var-row个
    if(row<var)//返回自由变元数
        return temp;

    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for(int i=var-1;i>=0;i--){//计算解集
        x[i]=a[i][var];
        for(int j=i+1;j<var;j++)
            x[i]^=(a[i][j]&&x[j]);
    }
    return 0;
}
int enumFreeX(int freeNum,int var){//枚举自由元，统计有解情况下1最少的个数
    int sta=(1<<(freeNum));//自由元的状态总数
    int res=INF;
    for(int i=0;i<sta;++i){//枚举状态
        int cnt=0;
        for(int j=0;j<freeNum;j++){//枚举自由元
            if(i&(1<<j)){
                cnt++;
                x[freeX[j]]=1;
            }else
                x[freeX[j]]=0;
        }
        for(int k=var-freeNum-1;k>=0;k--){//没有自由元的最下面一行
            int index=0;
            for(index=k;k<var;index++){//在当前行找到第一个非0自由元
                if(a[k][index])
                    break;
            }
            x[index]=a[k][var];
            for(int j=index+1;j<var;++j){//向后依次计算出结果
                if(a[k][j])
                    x[index]^=x[j];
            }
            cnt+=x[index];//若结果为1，则进行统计
        }
        res=min(res,cnt);
    }
    return res;
}


//

int prime[MAXN], tot;
bool vis[MAXN];
void Prime()
{
    for(int i = 2; i <= MAXN; i++) {
        if(!vis[i]) {
            prime[++tot] = i;
        }
        for(int j = 1; j <= tot ; j++) {
            if(i * prime[j] > MAXN) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;    //当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。 
        }
    }
}

ll q_pow(ll a, ll b, ll m){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1; 
    } 
    return ans;
}


ll b[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    Prime(); 
    int t, cas=0;
    cin>>t;
    while(t--)
    {    
        memset(a, 0, sizeof(a));
        int n;
        cin>>n;

        int equ = tot, var = n;

        for(int i = 0;  i< n; i++){
            cin>>b[i];
        }

        for(int i = 0;  i<tot; i++){
            for(int j = 0;  j < var; j++){
                while(b[j] % prime[i+1] == 0){
                    b[j] /= prime[i+1];
                    a[i][j]^=1;
                }
            }
        }


//        for(int i = 0;  i<tot; i++){
//            for(int j = 0;  j < var; j++){
//                
//                printf("%d ",a[i][j]);
//            }
//            printf("\n");
//        }


        int freeNum=Gauss(equ,var);//获取自由元


        ll ans = (q_pow(2*1LL, freeNum*1LL, MOD) - 1)%MOD;

        printf("Case #%d:\n",++cas);
        printf("%lld\n",ans);
     } 
}