#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define int long long

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define maxn 2000005

#define md 1000000007

int pri[10],f[2][maxn<<3],s,q,top=0;

int Dp()

{

    int now=0,pre=1;

    memset(f[now],0,sizeof f[now]);

    f[now][0]=1;

    F(i,1,top)

    {

        now^=1;pre^=1;memset(f[now],0,sizeof f[now]);

        int up=s/pri[i]-1;

        F(l,0,pri[i]-1)

        {

            int presum=0;

            for (int j=0;j<=(s*top-l)/pri[i];j++)

            {

                presum+=f[pre][j*pri[i]+l];presum%=md;

                if (j>=up+1) presum-=f[pre][(j-up-1)*pri[i]+l];

                f[now][j*pri[i]+l]=presum;

            }

        }

    }

    return now;

}

int ksm(int a,int b)

{

    int ret=1;

    for (;b;b>>=1,a=a*a%md) if (b&1) ret=ret*a%md;

    return ret;

}

int C(int n,int m)

{

    n=n+1; m=m-1;

    n=n+m-1;

    int ret=1;

    for(int i=n;i>=n-m+1;i--)

        ret=ret*(i%md)%md;

    F(i,1,m) ret=ret*ksm(i,md-2)%md;

    return ret;

}

signed main()

{

    scanf("%lld%lld",&s,&q);int x=s;

    F(i,2,sqrt(s))

    {

        if (s%i==0) s/=i,pri[++top]=i;

        if (s%i==0)

        {

            while(q--) printf("0\n");

            return 0;

        }

    }

    if (s>1) pri[++top]=s; s=x;

    int now=Dp();

    while(q--)

    {

        int ret=0;

        int n;scanf("%lld",&n);

        F(i,1,top) n-=pri[i];

        if (n<0) {printf("0\n"); continue;}

        int m=n/s,k=n-m*s;

        F(i,0,min(top,m))

            ret=(ret+f[now][i*s+k]*C(top+m-i-top,top%md)%md)%md;

        printf("%lld\n",(ret+md)%md);

    }

}