#include<iostream>
#include<cstdio>
#define N 128
#define M 53
#define W 59
#define mod 1000000007
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
long long m,n;
int q,ans,res=1,C[M+1][M+1],pws[M+1][M+1],scnt[N+1],delta[N+1],delta2[N+1],dp[N+1],DP[N+1],F[N+1];
struct matrix
{
	int d[N+1][N+1];
};
matrix zero,c,nw,e,pw[W+1];
matrix operator * (matrix a,matrix b)
{
	c=zero;
	for (int k=1;k<=res;++k)
		for (int i=1;i<=res;++i)
			for (int j=1;j<=res;++j)
				Adder(c.d[i][j],1ll*a.d[i][k]*b.d[k][j]%mod);
	return c;
}
int main()
{
	int cnt,d,rst,rst2;
	long long x;
	for (int i=0;i<=M;++i) C[i][0]=1;
	for (int i=1;i<=M;++i)
		for (int j=1;j<=i;++j)
			C[i][j]=MD(C[i-1][j-1]+C[i-1][j]);
	x=m=read(),q=read();
	for (int i=2;i*i<=m;++i)
		if (x%i==0)
		{
			cnt=0;
			while (x%i==0) x/=i,cnt++;
			scnt[cnt]++;
		}
	if (x!=1) scnt[1]++;
	for (int i=1;i<=M;++i) res*=(scnt[i]+1);
	for (int i=1;i<=res;++i) e.d[i][i]=1;
	for (int i=0;i<=M;++i)
	{
		pws[i][0]=1;
		for (int j=1;j<=M;++j) pws[i][j]=1ll*pws[i][j-1]*i%mod;
	}
	for (int i=1;i<=res;++i)
		for (int j=1;j<=res;++j)
		{
			d=i-1;
			for (int k=1;k<=M;++k) delta[k]=d%(scnt[k]+1),d/=(scnt[k]+1);
			d=j-1;
			for (int k=1;k<=M;++k) delta2[k]=d%(scnt[k]+1),d/=(scnt[k]+1);
			rst=rst2=1;
			for (int k=1;k<=M;++k) rst=1ll*rst*C[scnt[k]][delta2[k]]%mod*pws[k][delta2[k]]%mod,rst2=1ll*rst2*C[scnt[k]-delta[k]][delta2[k]]%mod*pws[k][delta2[k]]%mod;
			if (i==1) DP[j]=rst;
			Adder2(rst,-rst2),nw.d[i][j]=rst;
		}
	pw[0]=nw;
	for (int i=1;i<=W;++i) pw[i]=pw[i-1]*pw[i-1];
	while (q--)
	{
		n=read(),ans=0;
		for (int i=1;i<=res;++i) dp[i]=DP[i];
		for (int i=0;i<=W;++i)
			if (((n-1)>>i)&1)
			{
				for (int k=1;k<=res;++k) F[k]=0;
				for (int k=1;k<=res;++k)
					for (int t=1;t<=res;++t)
						Adder(F[t],1ll*dp[k]*pw[i].d[k][t]%mod);
				for (int k=1;k<=res;++k) dp[k]=F[k];
			}
		for (int i=1;i<=res;++i) Adder(ans,dp[i]);
		printf("%d\n",ans);
	}
	return 0;
}