FWT or WA70pts 死活过不去玄关

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=805,M=9,K=1<<16,mod=1e9+7;
int n,tg,l,q,w,p[M],a[M],pa[M],pw[N];
int tot,num[N],ret[N],f[N][K],g[N][K],h[K];
map<int,int>mp;

int qp(int a,int b){
    int ret=1;
    for(;b;b>>=1,(a*=a)%=mod)
        if(b&1)(ret*=a)%=mod;
    return ret;
}

int calc(int x){
    int ax=0;
    for(int i=1;i<=w;i++){
        if(x%pa[i]==0)ax|=(1<<(i+7));
        if(x%p[i])ax|=(1<<(i-1));
    }
    return ax;
}

void dfs(int u,int prod){
    if(u==w+1){if(prod<=n)num[++tot]=prod;return;}
    for(int i=0;i<=a[u];i++){
        if(prod>n)return;
        dfs(u+1,prod);
        prod*=p[u];
    }
}

void FMT_or(int*a,int typ=1){
    for(int i=1;i<K;i<<=1)
    for(int j=0;j<K;j+=i<<1)
    for(int k=0;k<i;k++)
        (a[i+j+k]+=a[j+k]*typ+mod)%=mod;
}

void solve(){
    int x;cin>>x;
    if(x%tg){cout<<"0\n";return;}x/=tg;
    if(l%x||x>n){cout<<"0\n";return;}
    int ax=calc(x),pos=lower_bound(num+1,num+tot+1,ax)-num;
    cout<<ret[pos]<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>tg>>l>>q;
    if(l%tg){
        while(q--)cout<<"0\n";
        return 0;
    }
    l/=tg,n/=tg;int tmp=l;
    for(int i=2;i*i<=tmp;i++){
        if(tmp%i!=0)continue;p[++w]=i;pa[w]=1;
        while(tmp%i==0){a[w]++;pa[w]*=p[w];tmp/=i;}
    }
    if(tmp){p[++w]=tmp;pa[w]=tmp;a[w]=1;}dfs(1,1);
    for(int i=1;i<=tot;i++){
        num[i]=calc(num[i]);
        mp[ num[i] ]++;
    }
    sort(num+1,num+tot+1);
    tot=unique(num+1,num+tot+1)-num-1;
    for(int i=1;i<=tot;i++)
        pw[i]=qp(2,mp[ num[i] ])-1;
    f[0][0]=g[tot+1][0]=1;
    for(int i=0;i<tot;i++)for(int j=0;j<K;j++){
        if(!f[i][j])continue;
        (f[i+1][j]+=f[i][j])%=mod;
        (f[i+1][ j|num[i+1] ]+=f[i][j]*pw[i+1]%mod)%=mod;
    }
    for(int i=tot+1;i>1;i--)for(int j=0;j<K;j++){
        if(!g[i][j])continue;
        (g[i-1][j]+=g[i][j])%=mod;
        (g[i-1][ j|num[i-1] ]+=g[i][j]*pw[i-1]%mod)%=mod;
    }
    for(int i=0;i<=tot+1;i++)FMT_or(f[i]),FMT_or(g[i]);
    int mx=(1<<w)-1;mx+=(mx<<8);
    for(int i=1;i<=tot;i++){
        for(int j=0;j<K;j++)h[j]=f[i-1][j]*g[i+1][j]%mod;
        FMT_or(h,-1);for(int j=0;j<K;j++)if((j|num[i])==mx)ret[i]+=h[j];
        (ret[i]*=qp(2,mp[ num[i] ]-1))%=mod;
    }
    while(q--)solve();
}