// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;

#define var const auto &
constexpr int P=1e9+7;
constexpr auto mul(var a,var b) { return 1ll*a*b%P; }
constexpr auto mul(var a,var ...b) { return mul(a,mul(b...)); }
constexpr auto add(var a,var b) { return (a+b)>=P?a+b-P:a+b; }
constexpr auto sub(var a,var b) { return a-b<0?a-b+P:a-b; }
constexpr void add$(auto &a,var b) { a=add(a,b); }
constexpr void mul$(auto &a,var b) { a=mul(a,b); }
constexpr qpow(int a,int b)
{
   int res=1;
   for(;b;b>>=1,mul$(a,a)) if(b&1) mul$(res,a);
   return res;
}

using LL=long long;
const int N=400,M=64;
LL m;
int q,n,C[M][M];
map<int,int> mp;

using Arr=array<int,N>;
using Mat=array<Arr,N>;

Mat pw[M];

Mat operator * (const Mat &x, const Mat &y)
{
   Mat res{};
   for(int i=0;i<n;i++) for(int j=0;j<n;j++)
      for(int k=0;k<n;k++)
      {
         add$(res[i][j],mul(x[i][k],y[k][j]));
      }
   return res;
}
Arr operator * (const Arr &x, const Mat &y)
{
   Arr res{};
   for(int i=0;i<n;i++) for(int j=0;j<n;j++)
      add$(res[j],mul(x[i],y[i][j]));
   return res;
}

int main()
{
   for(int i=C[0][0]=1;i<M;i++)
      for(int j=C[i][0]=1;j<=i;j++)
         C[i][j]=add(C[i-1][j],C[i-1][j-1]);

   cin>>m>>q;
   for(int i=2;i<=sqrt(m);i++) if(m%i==0)
   {
      int cnt=0; for(;m%i==0;m/=i) cnt++;
      mp[cnt]++;
   }
   if(m!=1) mp[1]++;
   vector<pair<int,int>> S;
   for(auto [i,j]:mp) S.push_back({i,j});
   // cerr<<"s.size()="<<S.size()<<endl;
   vector<array<int,14>> t;
   function<void(int)> dfs=[&](unsigned x)
   {
      static array<int,14> cur;
      if(x==S.size())
      {
         t.push_back(cur);
         return;
      }
      for(int i=0;i<=S[x].second;i++)
         cur[x]=i, dfs(x+1);
   };
   dfs(0); n=t.size();
   // printf("t.size()=%lld\n",t.size());
   pw[0]={};
   for(int i=0;i<n;i++) for(int j=0;j<n;j++)
   {
      auto x=t[i],y=t[j];
      int ret=1,dec=1;
      for(size_t i=0;i<S.size();i++)
         mul$(ret,mul(C[S[i].second][y[i]],qpow(S[i].first,y[i])));
      for(size_t i=0;i<S.size();i++)
         mul$(dec,mul(C[S[i].second-x[i]][y[i]],qpow(S[i].first,y[i])));
      pw[0][i][j]=sub(ret,dec);
      // printf("base[%d][%d]=%d\n",i,j,pw[0][i][j]);
   }
   for(int i=1;i<M;i++)
   {
      pw[i]=pw[i-1]*pw[i-1];
   }
   while(q--)
   {
      LL x; cin>>x;
      int sum=x==1;
      Arr ans{}; ans[n-1]=1;
      for(int i=0;i<M;i++) if(x>>i&1)
         ans=ans*pw[i];
      for(int i=0;i<n;i++) add$(sum,ans[i]);
      cout<<sum<<'\n';
   }
   return 0;
}

answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:7:20: note: in expansion of macro ‘var’
    7 | constexpr auto mul(var a,var b) { return 1ll*a*b%P; }
      |                    ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:7:26: note: in expansion of macro ‘var’
    7 | constexpr auto mul(var a,var b) { return 1ll*a*b%P; }
      |                          ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:8:20: note: in expansion of macro ‘var’
    8 | constexpr auto mul(var a,var ...b) { return mul(a,mul(b...)); }
      |                    ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:8:26: note: in expansion of macro ‘var’
    8 | constexpr auto mul(var a,var ...b) { return mul(a,mul(b...)); }
      |                          ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:9:20: note: in expansion of macro ‘var’
    9 | constexpr auto add(var a,var b) { return (a+b)>=P?a+b-P:a+b; }
      |                    ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:9:26: note: in expansion of macro ‘var’
    9 | constexpr auto add(var a,var b) { return (a+b)>=P?a+b-P:a+b; }
      |                          ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:10:20: note: in expansion of macro ‘var’
   10 | constexpr auto sub(var a,var b) { return a-b<0?a-b+P:a-b; }
      |                    ^~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:10:26: note: in expansion of macro ‘var’
   10 | constexpr auto sub(var a,var b) { return a-b<0?a-b+P:a-b; }
      |                          ^~~
answer.code:11:21: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
   11 | constexpr void add$(auto &a,var b) { a=add(a,b); }
      |                     ^~~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:11:29: note: in expansion of macro ‘var’
   11 | constexpr void add$(auto &a,var b) { a=add(a,b); }
      |                             ^~~
answer.code:12:21: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
   12 | constexpr void mul$(auto &a,var b) { a=mul(a,b); }
      |                     ^~~~
answer.code:5:19: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
    5 | #define var const auto &
      |                   ^~~~
answer.code:12:29: note: in expansion of macro ‘var’
   12 | constexpr void mul$(auto &a,var b) { a=mul(a,b); }
      |                             ^~~
answer.code:13:11: error: ISO C++ forbids declaration of ‘qpow’ with no type [-fpermissive]
   13 | constexpr qpow(int a,int b)
      |           ^~~~