#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5,M=220,mod=1e9+7,B=8;
long long m,n;
int q,s=1,ans[M];
bool pd[N];
int prime[N];
int cnt;

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

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


struct mtr{
	int t[M][M];
}P,A,R[M][B];

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

mtr operator *(mtr a,mtr b){
	mtr tot;
	for(int i=1;i<=s;i++)
		for(int j=1;j<=s;j++)
			tot.t[i][j]=0;
	for(int i=1;i<=s;i++)
		for(int k=1;k<=s;k++)
			for(int j=1;j<=s;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 & 1ll) tot=a*tot;
		a=a*a;
		x>>=1ll;
	}
	return tot;
}

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


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