HDU6439

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;
const int N=1e6+7;

inline int add(int a,int b){
    return (a+=b)>=p?a-p:a;
}

inline int sub(int a,int b){
    return (a-=b)<0?a+p:a;
}

inline ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ans;
}

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int Arr[N];
int f[N];
int inv[55];

inline void pre(int x){
    f[1]=1;
    for(int i=1;i<=x+1;++i){
        Arr[i]=qpow(i,x);
    }
    for(int i=1;i<=x+1;++i){
        for(int j=1;j<=x-i+1;++j){
            Arr[j]=sub(Arr[j+1],Arr[j]);
        }
        f[i+1]=Arr[1];
    }
}


inline int S(int n,int x){
    ll ret=0,C=1;
    for(int i=0;i<=x+1;++i){
        ret+=C*f[i]%p;
        C=C*inv[i+1]%p*(n-i)%p;
    }
    return ret%p;
}

int tot;
int pri[N];
bool mark[N];
int mu[N];
int Sum[N];

map<int,int>mp;
inline int getsum(int n){
    if(n<N)return Sum[n];
    if(mp[n])return mp[n];
    ll ans=1;
    for(int i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        ans-=(ll)(j-i+1)*getsum(n/i);
    }
    return mp[n]=ans;
}

inline void init(int n=N-1){
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!mark[i])pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot;++j){
            int tmp=i*pri[j];
            if(tmp>n)break;
            mark[tmp]=1;
            if(i%pri[j])mu[tmp]=-mu[i];
            else {
                mu[tmp]=0;break;
            }
        }
    }
    for(int i=1;i<=n;++i){
        Sum[i]=Sum[i-1]+mu[i];
    }
    inv[1]=1;
    for(int i=2;i<=51;++i){
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    }
}

int cnt;
ll ans;

vector<int>factor;

inline void dfs(int x,int y,int n){
    if(x==factor.size()){
        ans+=y*S(n,cnt);
        return ;
    }
    dfs(x+1,-y,n/factor[x]);
    dfs(x+1,y,n);
}

int main(){
    init();
    int T;r(T);
    for(int cas=1;cas<=T;++cas){
        int n,k;r(k),r(n);
        int g=0;
        ans=cnt=0;
        for(int i=1;i<=k;++i){
            int x;r(x);
            if(~x)g=gcd(g,x);
            else ++cnt;
        }
        pre(cnt);
        if(g){
            factor.clear();
            for(int i=1;i<=tot;++i){
                int t=pri[i];
                if(t*t>g)break;
                if(g%t==0){
                    factor.push_back(t);
                    while(g%t==0)g/=t;
                }
            }
            if(g>1)factor.push_back(g);
            dfs(0,1,n);
        }
        else {
            for(int i=1,j;i<=n;i=j+1){
                j=n/(n/i);
                ans+=(ll)(getsum(j)-getsum(i-1))*S(n/i,cnt)%p;
            }
        }
        printf("Case #%d: %lld\n",cas,(ans%p+p)%p);
    }
}