#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
constexpr int p=1e9+7,N=310;
typedef std::vector<int> poly;
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
poly operator*(const poly &a,const poly &b){
	int la=a.size(),lb=b.size();
	int l=la+lb-1;poly ret(l);
	static unsigned long long ans[N<<1];
	for(int i=0;i<l;++i) ans[i]=0;
	for(int i=0;i<la;++i){
		for(int j=0;j<lb;++j){
			ans[i+j]+=1ull*a[i]*b[j];
		}
		if((i%18)==0){
			for(int j=0;j<l;++j) ans[j]%=p;
		}
	}
	for(int j=0;j<l;++j) ret[j]=ans[j]%p;
	return ret;
}
poly operator%(poly a,const poly &b){
	if(a.size()<b.size()) return a;
	int la=a.size(),lb=b.size();
	int num=fp(b.back(),p-2);
	static unsigned long long ans[N<<1];
	for(int i=0;i<la;++i) ans[i]=a[i];
	a.resize(lb-1);
	for(int i=la-1;i>=lb-1;--i){
		int val=(p-ans[i]%p)*num%p;
		for(int j=0;j<lb;++j) ans[i-j]+=1ull*val*b[lb-1-j];
		if((i%18)==0){
			for(int j=0;j<i;++j) ans[j]%=p;
		}
	}
	for(int i=0;i<lb-1;++i) a[i]=ans[i]%p;
	return a;
}
poly fp(const poly &a,long long b,const poly &c){poly ans({1}),off=a;while(b){if(b&1) ans=ans*off%c;off=off*off%c;b>>=1;}return ans;}
inline int W(int a){return a>=p?a-p:a;}
poly bm(const poly &in){
	poly R0={},R1={0};int d=W(p-in[0]),f=0;
	int len=in.size();
	for(int i=1;i<len;++i){
		unsigned long long cur=0;
		int l=R1.size();
		int pos=0;
		for(;pos+18<=l;pos+=18){
			for(int j=0;j<18;++j) cur+=1ull*R1[pos+j]*in[i-pos-j-1];
			cur%=p;
		}
		while(pos<l) cur+=1ull*R1[pos]*in[i-pos-1],++pos;
		int cm=W(int(cur%p)-in[i]+p);
		if(cm){
			int val=1ll*fp(d,p-2)*cm%p,pv=W(p-val);
			poly R=R1;
			int len=i-f-1;if(R.size()<len+1+R0.size()) R.resize(len+1+R0.size());
			R[len]=W(R[len]+val);l=R0.size();
			for(int i=0;i<l;++i) R[len+i+1]=(R[len+i+1]+1ll*pv*R0[i])%p;
			R0=R1;R1=R;
			d=cm;f=i;
		}
	}
	return R1;
}
poly operator+(const poly &a,const poly &b){
	int lb=b.size();
	poly ret(a);ret.resize(max<int>(a.size(),lb));
	for(int i=0;i<lb;++i) ret[i]=W(ret[i]+b[i]);
	return ret;
}
poly operator-(const poly &a,const poly &b){
	int lb=b.size();
	poly ret(a);ret.resize(max<int>(a.size(),lb));
	for(int i=0;i<lb;++i) ret[i]=W(ret[i]-b[i]+p);
	return ret;
}
constexpr int PR=100000010,PS=10000010,len=300;
#include <bitset>
bitset<PR> vis;int ps[PS],pc,alpha[20],acnt,num[len+10][20];
int main(){
	for(int i=2;i<PR;++i){
		if(!vis[i]) ps[++pc]=i;
		for(int j=1;j<=pc && ps[j]*i<PR;++j){
			vis[ps[j]*i]=true;
			if((i%ps[j])==0) break;
		}
	}
	long long m;int q,s=1;scanf("%lld%d",&m,&q);
	for(int i=1;i<=pc && 1ll*ps[i]*ps[i]<=m;++i) if((m%ps[i])==0){
		int c=0;
		while((m%ps[i])==0) ++c,m/=ps[i];
		alpha[++acnt]=c;
		s*=(c+1);
	}
	if(m>1) alpha[++acnt]=1;
	for(int i=1;i<=acnt;++i) num[0][i]=1,num[1][i]=alpha[i]+1;
	for(int i=2;i<=len;++i){
		for(int j=1;j<=acnt;++j) num[i][j]=(num[i-1][j]+1ll*num[i-2][j]*alpha[j])%p;
	}
	poly G(len+1);
	for(int i=0;i<=len;++i){
		int cur=(i&1^1)?(p-1):1;
		for(int j=1;j<=acnt;++j) cur=1ll*cur*num[i][j]%p;
		G[i]=cur;
	}
	G[0]=0;
	// for(int i=0;i<=10;++i) printf("%d ",G[i]);printf("\n");
	poly F=bm(G);
	// for(int i:F) printf("%d ",i);printf("\n");
	poly R=(poly({1})-F*poly({0,1}))*G;R.resize(F.size());
	poly B=(poly({1})-F*poly({0,1}));
	poly T=B-R;
	// for(int i:T) printf("%d ",i);printf("\n");
	poly TR(T);reverse(TR.begin(),TR.end());
	int l=B.size()-1;
	poly B0(l+1);
	for(int i=0;i<=l;++i){
		int cur=0;
		for(int j=1;j<=i;++j) cur=(cur+1ll*B0[i-j]*T[j])%p;
		B0[i]=W(B[i]-cur+p);
	}
	// for(int i:B0) printf("%d ",i);printf("\n");
	// for(int i:TR) printf("%d ",i);printf("\n");
	while(q--){
		long long n;scanf("%lld",&n);
		auto res=fp({0,1},n-1,TR);
		int cur=0;
		// for(int i:res) printf("%d ",i);printf("\n");
		res.resize(l);
		for(int i=0;i<l;++i) cur=(cur+1ll*B0[i+1]*res[i])%p;
		printf("%d\n",cur);
	}
	return 0;
}