#include <bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
long long m;
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],sum[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]-=(A[n][i][j]>=Mod)?Mod:0;
	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]-=(C[i][j]>=Mod)?Mod:0;
	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++) {
	  	  A[0][j][i]=1;
	  	  int s=1,ss=1;
	      for (int k=1;k<=nu;k++) {
	      		s=1LL*s*c[q[k]][a[j][k]]*f[h[k]][a[j][k]];
	      		ss=1LL*ss*c[q[k]-a[i][k]][a[j][k]]*f[h[k]][a[j][k]];
	      	}
	      A[0][j][i]=(s-ss+Mod)%Mod;
	  }
	for (int i=1;i<=60;i++) Mul(i);
	for (int i=1;i<=num;i++) {
		sum[i]=1; 
	    for (int j=1;j<=nu;j++)
	      sum[i]=1LL*sum[i]*c[q[j]][a[i][j]]%Mod*f[h[j]][a[i][j]]%Mod;
	}
	long long n;
	for (int i1=1;i1<=Q;i1++) {
		scanf("%lld",&n);
		for (int i=1;i<=num;i++)
		  for (int j=1;j<=num;j++)
		    M[i][j]=0;
		for (int i=1;i<=num;i++) M[i][i]=1;
		n--;
		for (long long i=n;i>0;i-=i&(-i))
		  Mul_(log2(i&(-i)));
		int ans=0;
		for (int i=1;i<=num;i++) {
			int ss=0;
		    for (int j=1;j<=num;j++) 
		      ss+=M[j][i],ss-=(ss>=Mod)?Mod:0;
		    ans=(ans+1LL*sum[i]*ss%Mod)%Mod;
		}
		if (n==0) ans++;
		printf("%d\n",ans);
	}
	return 0;
}