被卡常数的代码：
#include<bits/stdc++.h>
#define int long long
#define N 300010
#define mo 1000000007
#pragma GCC optimize(3)
int p[N],vi[N],ct,b[N],d[N],e[N],cc,s[N],g[N],n,T,a[N];
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=x*x%mo)
if(y&1)
r=r*x%mo;
return r;
}
void si(){
for(int i=2;i<N;i++){
if(!vi[i]){
p[++ct]=i;
}
for(int j=1;j<=ct&&p[j]*i<N;j++){
vi[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
void fj(int x){
for(int i=1;i<=ct;i++){
int c=0;
while(x%p[i]==0){
x/=p[i];
c++;
}
if(c){
d[++cc]=p[i];
e[cc]=c;
}
}
}
void qv(int *a,int t){
if(t==1){
for(int i=0;i<cc;i++)
for(int j=0;j<(1<<cc);j++)
if(j&(1<<i))
a[j]=(a[j]+a[j-(1<<i)])%mo;
}
else{
for(int i=0;i<cc;i++)
for(int j=0;j<(1<<cc);j++)
if(j&(1<<i))
a[j]=(a[j]-a[j-(1<<i)]+mo)%mo;
}
}
signed main(){
si();
scanf("%lld%lld",&n,&T);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
while(T--){
cc=0;
int x,k,p;
scanf("%lld%lld%lld",&x,&k,&p);
for(int i=1;i<=n;i++){
b[i]=gcd(a[i],p);
s[i]=0;
}
fj(p);
for(int i=0;i<(1<<cc);i++)
g[i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=cc;j++){
int c1=0,c2=0;
int y=x,z=b[i];
while(y%d[j]==0){
y/=d[j];
c1++;
}
while(z%d[j]==0){
z/=d[j];
c2++;
}
if(c2<=c1)
s[i]+=(1<<(j-1));
}
}
for(int i=1;i<=n;i++)
g[s[i]]++;
qv(g,1);
for(int i=0;i<(1<<cc);i++)
g[i]=qp((1+qp(k,mo-2))%mo,g[i])%mo;
qv(g,-1);
printf("%lld
",qp(k,n)*g[(1<<cc)-1]%mo);
}
}