#include<bits/stdc++.h> #define ll long long using namespace std; const int LM=101,LEN=16,B=(1<<LEN); vector<int> p; int mod; class BarrettModulo { private: uint64_t p; // The modulus uint64_t m; // Precomputed value for optimization public: BarrettModulo(uint64_t modulus) : p(modulus) { m = ((__int128)1 << 64) / p; } uint64_t operator()(uint64_t x) const { uint64_t res = x - ((__int128(x) * m) >> 64) * p; return (res >= p) ? (res - p) : res; } }; BarrettModulo fm(1e9+7); void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} void Sub(int &a,int b){a-=b;if(a<0) a+=mod;} bool isp[LM+10]; int C[LM+10][LM+10],pw2[4][B+10]; void init(){ for(int i=2;i<=LM;i++){ if(!isp[i]) p.push_back(i); for(auto j:p){ if(i*j>LM) break; isp[i*j]=1; if(i%j==0) break; } } C[0][0]=1; for(int i=1;i<=LM;i++){ C[i][0]=1; for(int j=1;j<=LM;j++){ C[i][j]=fm((ll)C[i-1][j]+C[i-1][j-1]); } } for(int i=0;i<4;i++){ pw2[i][0]=1; for(int j=1;j<=B;j++){ if(i) pw2[i][j]=fm(1ll*pw2[i][j-1]*pw2[i-1][B]); else pw2[i][j]=fm(2ll*pw2[i][j-1]); } } } int p2(ll b){ int x=1; for(int i=0;i<4;i++,b>>=LEN)x=fm(1ll*x*pw2[i][b&(B-1)]); return x; } ll n;int ans=0; int buc[LM+10]; void dfs(int id,int val,ll cd){ if(id>LM){ //cout<<ans<<' '<<val<<' '<<cd<<endl; ans=fm(ans+1ll*val*(p2(cd)+mod-1)); //cout<<ans<<endl; return ; } for(int i=0;i<=buc[id];i++){ int tval=fm(1ll*val*C[buc[id]][i]);ll tcd=cd; for(int j=0;i+j<=buc[id];j++){ dfs(id+1,fm(1ll*tval*C[buc[id]-i][j]),tcd); tcd/=(id+1),tcd*=(id-1); }val=fm(1ll*val*(mod-2));cd/=(id+1),cd*=id; } } map<ll,int> mp; void slv(){ cin>>n;ll tn=n; if(mp.count(n)){ cout<<mp[n]<<'\n'; return ; } memset(buc,0,sizeof(buc)); ll cd=1;ans=0; for(auto ed:p){ if(n%ed!=0) continue; int cnt=0; while(n%ed==0) n/=ed,cnt++; buc[cnt]++;cd*=(cnt+1); }dfs(1,1,cd);cout<<ans<<'\n'; mp[tn]=ans; } int main(){ //freopen("pain.in","r",stdin); //freopen("pain.out","w",stdout); int t;cin>>t>>mod; fm=BarrettModulo(mod); init(); while(t--) slv(); return 0; }