#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<random>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#include<assert.h>

#define int long long
#define fi first
#define se second
#define max Max
#define min Min
#define abs Abs
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define pb(x) push_back(x)
#define lowbit(x) ((x)&(-(x)))
#define fan(x) ((((x)-1)^1)+1)
#define mp(x,y) make_pair(x,y)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define SZ(x) ((int)(x.size()))
#define INF 0x3f3f3f3f

using namespace std;

inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
	return ans*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x/10) write(x/10);
	putchar((char)(x%10)+'0');
}

template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a<b?a:b;}
template<typename T,typename TT> inline T Max(T a,TT b){return a<b?b:a;}

const int N=205,mod=998244353;
int n,m,q,k,a[N],b[N],c[N],C[N][N],cnt;

struct Matrix
{
	int n,m,c[N][N];
	Matrix()
	{
		memset(c,0,sizeof(c));
	}
	Matrix(int a,int b)
	{
		n=a;m=b;
		memset(c,0,sizeof(c));
	}
	Matrix operator * (const Matrix p)
	{
		Matrix res(n,p.n);
		assert(m==p.n);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=p.m;++j)
				for(int k=1;k<=p.n;++k)
					res.c[i][j]=(res.c[i][j]+c[i][k]*p.c[k][j]%mod)%mod;
		return res;
	}
}pw[60],ans;

vector<int> now;
vector<vector<int> > state;

void dfs(int u)
{
	if(u==cnt+1)
	{
		state.push_back(now);++k;
		return;
	}
	for(int i=0;i<=b[u];++i)
	{
		now.push_back(i);
		dfs(u+1);
		now.pop_back(); 
	}
}

inline int q_pow(int a,int b)
{
	int c=1;
	while(b)
	{
		if(b&1) c=a*c%mod;
		a=a*a%mod;b>>=1;
	}
	return c;
}

signed main()
{
	m=read();q=read();
	for(int i=0;i<=200;++i)
		for(int j=0;j<=i;++j)
			if(j==0) C[i][j]=1;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(int i=2;i*i<=m;++i)
		if(m%i==0)
		{
			++k;
			while(m%i==0)
				m/=i,c[k]++;
		}
	if(m!=1) c[++k]=1;
	sort(c+1,c+1+k);
	for(int i=1;i<=k;++i)
	{
		if(c[i]!=c[i-1])
			a[++cnt]=c[i],b[cnt]=1;
		else b[cnt]++;
	}
	k=0;dfs(1);
	pw[0].n=pw[0].m=k;
	for(int i=1;i<=k;++i)
		for(int j=1;j<=k;++j)
		{
			int g[2]={1,0};
			for(int p=1;p<=cnt;++p)
			{
				int all=C[b[p]][state[j-1][p-1]]*q_pow(a[p],state[j-1][p-1])%mod;
				int w0=(b[p]-state[i-1][p-1]<state[j-1][p-1]?0:C[b[p]-state[i-1][p-1]][state[j-1][p-1]]*q_pow(a[p],state[j-1][p-1])%mod),w1=(all-w0+mod)%mod;
				g[1]=(g[1]*all+g[0]*w1)%mod;
				g[0]=g[0]*w0%mod;
			}
			pw[0].c[j][i]=g[1];
		}
	for(int i=1;i<=59;++i)
		pw[i]=pw[i-1]*pw[i-1];
	while(q--)
	{
		n=read()-1;
		ans.n=k;ans.m=1;
		for(int i=1;i<=k;++i)
		{
			int tmp=1;
			for(int j=1;j<=cnt;++j)
				tmp=tmp*C[b[j]][state[i-1][j-1]]%mod*q_pow(a[j],state[i-1][j-1])%mod;
			ans.c[i][1]=tmp;
		}
		for(int i=0;i<=59;++i)
			if((n>>i)&1)
				ans=pw[i]*ans;
		int Ans=0;
		for(int i=1;i<=k;++i)
			Ans=(Ans+ans.c[i][1])%mod;
		write(Ans);puts("");
	}
	return 0;
}