#include<bits/stdc++.h>
using namespace std;
const long long N=1e8+5,M=110,mod=1e9+7;
long long m,q,s=1,n;

bool pd[N];
int prime[N];
long long cnt;

long long mul[N],inv[N];
long long C(long long m,long long n){
	if(m<0 || n<0 || m<n) return 0;
	return 1ll*mul[m]*inv[n]%mod*inv[m-n]%mod;
}
long long ksm(long long f,long long x){
	long long tot=1;
	while(x){
		if(x & 1ll) tot=1ll*tot*f%mod;
		f=1ll*f*f%mod;
		x>>=1ll;
	}
	return tot;
}
void init(long long lim){
	mul[0]=inv[0]=1;
	for(long long i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*i%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(long long i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	
	pd[1]=1;
	for(long long i=2;i<=lim;i++){
		if(!pd[i]) prime[++cnt]=i;
		for(long long j=1;j<=cnt && i*prime[j]<=lim;j++){
			pd[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

long long tmp[M],num[M],e[M],id;


struct mtr{
	long long t[M][M];
}P,A;

mtr getnew(){
	mtr tmp;
	for(long long i=1;i<M;i++)
		for(long long j=1;j<M;j++)
			tmp.t[i][j]=0;
	for(long long j=1;j<=s;j++) tmp.t[j][j]=1;
	return tmp;
}

mtr operator *(mtr a,mtr b){
	mtr tot;
	memset(tot.t,0,sizeof(tot.t));
	for(long long i=1;i<M;i++)
		for(long long k=1;k<M;k++)
			for(long long j=1;j<M;j++)
				tot.t[i][j]=(tot.t[i][j]+1ll*a.t[i][k]*b.t[k][j]%mod)%mod;
	return tot;
}

mtr ksm(mtr a,long long x){
	mtr tot=getnew();
	while(x){
		if(x&1) tot=a*tot;
		a=a*a;
		x>>=1ll;
	}
	return tot;
}

long long a[M],b[M],val[M];

int main(){
	init(N-5);
	cin>>m>>q;
	long long x=m;
	for(long long i=1;i<=cnt && prime[i]<=x;i++){
		if(x%prime[i]) continue;
		long long tot=0;
		while(x%prime[i]==0) tot++,x/=prime[i];
		tmp[tot]++;
	}
	if(x>1) tmp[1]++;
	
	for(long long i=1;i<=80;i++)
		if(tmp[i]){
			num[++id]=tmp[i];
			e[id]=i;
			s*=num[id]+1;
		}
	
	
	
	for(long long i=1;i<=s;i++){
		for(long long j=1;j<=s;j++){
			long long x=i-1;
			for(long long t=1;t<=id;t++) a[t]=x%(num[t]+1),x/=(num[t]+1);
			
			long long y=j-1;
			for(long long t=1;t<=id;t++) b[t]=y%(num[t]+1),y/=(num[t]+1);
			
			long long sum=1,tot=1;
			for(long long t=1;t<=id;t++) sum=sum*C(num[t],b[t])%mod*ksm(e[t],b[t])%mod;
			for(long long t=1;t<=id;t++){
				if(a[t]+b[t]>num[t]){
					tot=0;
					break;
				}
				tot=tot*C(num[t]-a[t],b[t])%mod*ksm(e[t],b[t])%mod;
			}
			P.t[i][j]=(sum+mod-tot)%mod;
		}
	}
	
	for(long long i=1;i<=s;i++){
		long long x=i-1;
		for(long long t=1;t<=id;t++) a[t]=x%(num[t]+1),x/=(num[t]+1);
		long long tot=1;
		for(long long t=1;t<=id;t++)
			tot=tot*C(num[t],a[t])%mod*ksm(e[t],a[t])%mod;
		val[i]=tot;
	}
	for(long long i=1;i<=s;i++) A.t[i][1]=1;
	
	while(q--){
		long long ans=0;
		cin>>n;
		mtr Q=ksm(P,n-1)*A;
		for(long long i=1;i<=s;i++) ans=(ans+Q.t[i][1]*val[i]%mod)%mod;
		cout<<ans<<endl;
	}
	
}