#include <bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
long long m,n;
int nu,Q,p[20],q[20],h[20],f[65][20],num,A[65][260][260],M[260][260],tmp[20],c[20][20],a[260][20],C[260][260];
bool fla;
void dfs(int k)
{
	if (k>nu) {
		if (!fla) {fla=true;return;}
		num++;
		for (int i=1;i<=nu;i++)
		  a[num][i]=tmp[i];
		return ;
	}
	for (int i=0;i<=q[k];i++) {
	    tmp[k]=i;
	    dfs(k+1);
	}
	return;
}
void Mul(int n)
{
	for (int i=1;i<=num;i++)
	  for (int j=1;j<=num;j++)
	    for (int k=1;k<=num;k++)
	      A[n][i][j]+=1LL*A[n-1][i][k]*A[n-1][k][j]%Mod,A[n][i][j]%=Mod;
	return ;
}
void Mul_(int n)
{
	for (int i=1;i<=num;i++)
	  for (int j=1;j<=num;j++)
	    C[i][j]=0; 
	for (int i=1;i<=num;i++)
	  for (int j=1;j<=num;j++)
	    for (int k=1;k<=num;k++)
	      C[i][j]+=1LL*A[n][i][k]*M[k][j]%Mod,C[i][j]%=Mod;
	for (int i=1;i<=num;i++)
	  for (int j=1;j<=num;j++)
	    M[i][j]=C[i][j];
	return ;
}
int main()
{
	scanf("%lld%d",&m,&Q);
	int t=0;
	for (int i=2;i<=sqrt(m);i++) 
	  if (m%i==0) {
	  	  t++;
	  	  while (m%i==0) p[t]++,m/=i;
	  }
	if (m>1) p[++t]=1;
	sort(p+1,p+t+1);
	for (int i=1;i<=t;i++)
	  if (p[i]!=p[i-1]) q[++nu]=1,h[nu]=p[i];
	    else q[nu]++;
	for (int i=1;i<=60;i++) {
		f[i][0]=1;
		for (int j=1;j<=t;j++)
		  f[i][j]=1LL*f[i][j-1]*i%Mod;
	}
	for (int i=0;i<=t;i++) {
		c[i][0]=1;
		for (int j=1;j<=i;j++)
		  c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
	}
	fla=false;
	dfs(1);
	for (int i=1;i<=num;i++) 
	  for (int j=1;j<=num;j++) {
	  	  fla=false;A[0][j][i]=1;
	      for (int k=1;k<=nu;k++) {
	      		if (a[j][k]==0) continue;
	      		if (a[j][k]>0&&a[i][k]>0) fla=true; 
	    	    if (a[j][k]>=a[i][k]) 
	    	      A[0][j][i]=1LL*A[0][j][i]*c[q[k]-a[i][k]][a[j][k]-a[i][k]]%Mod*f[h[k]][a[j][k]]%Mod;
	            else A[0][j][i]=1LL*A[0][j][i]*c[a[i][k]][a[j][k]]%Mod*f[h[k]][a[j][k]]%Mod;
	      	}
	      if (!fla) A[0][j][i]=0;
	  }
	for (int i=1;i<=60;i++)
	  Mul(i);
	for (int i1=1;i1<=Q;i1++) {
		scanf("%lld",&n);
		memset(M,0,sizeof(M));
		for (int i=1;i<=num;i++)
			M[i][i]=1;
		n--;
		for (int i=0;i<=60;i++)
		  if ((n>>i)&1) Mul_(i);
		int ans=0;
		for (int i=1;i<=num;i++) {
			int ss=1;
			for (int j=1;j<=nu;j++)
			  ss=1LL*ss*c[q[j]][a[i][j]]%Mod*f[h[j]][a[i][j]]%Mod;
		    for (int j=1;j<=num;j++) 
		      ans=(ans+1LL*M[j][i]*ss%Mod)%Mod;
		}
		if (n==0) ans++;
		printf("%d\n",ans);
	}
	return 0;
}