#include <bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
long long m;
int nu,Q,p[20],t,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;
long long read()
{
	char ch;
	long long aqq=0;
	ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') aqq=aqq*10+int(ch-48),ch=getchar();
	return aqq;
}
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 (register int i=0;i<=q[k];++i) {
	    tmp[k]=i;
	    dfs(k+1);
	}
	return;
}
void Mul(int n)
{
	for (register int i=1;i<=num;++i)
	  for (register int j=1;j<=num;++j)
	    for (register 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 (register int i=1;i<=num;i++)
	  for (register int j=1;j<=num;j++)
	    C[i][j]=0;
	for (register int i=1;i<=num;++i)
	  for (register int j=1;j<=num;++j)
	    for (register 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 (register int i=1;i<=num;++i)
	  for (register int j=1;j<=num;++j)
	    M[i][j]=C[i][j];
	return ;
}
int main()
{
	m=read();Q=read();
	for (register 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 (register int i=1;i<=t;++i)
	  if (p[i]!=p[i-1]) q[++nu]=1,h[nu]=p[i];
	    else q[nu]++;
	for (register int i=1;i<=59;++i) {
		f[i][0]=1;
		for (int j=1;j<=t;++j)
		  f[i][j]=1LL*f[i][j-1]*i%Mod;
	}
	for (register int i=0;i<=t;++i) {
		c[i][0]=1;
		for (register int j=1;j<=i;++j)
		  c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
	}
	dfs(1);
	for (register int i=1;i<=num;++i) 
	  for (register int j=1;j<=num;++j) {
	  	  A[0][j][i]=1;
	  	  long long s=1,ss=1;
	      for (register 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);A[0][j][i]-=(A[0][j][i]>=Mod)?Mod:0;
	  }
	for (register int i=1;i<=59;++i) Mul(i);
	for (register int i=1;i<=num;++i) {
		sum[i]=1; 
	    for (register 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 (register int i1=1;i1<=Q;++i1) {
		n=read();
		for (register int i=1;i<=num;++i)
		  for (register int j=1;j<=num;++j)
		    M[i][j]=0;
		for (register 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 (register int i=1;i<=num;++i) {
			int ss(0);
		    for (register int j=1;j<=num;++j) 
		      ss+=M[j][i],ss-=(ss>=Mod)?Mod:0;
		    ans+=1LL*sum[i]*ss%Mod;ans-=(ans>=Mod)?Mod:0;
		}
		if (n==0) ans++;
		printf("%d\n",ans);
	}
	return 0;
}