#include "bits/stdc++.h"
#define rep(i,a,n) for(auto i=a;i<=n;i++)
#define per(i,a,n) for(auto i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define all(A) A.begin(),A.end()
#define sz(A) (int)A.size()
template<class T> inline bool chmax(T &a, T b) { if(a < b) {a = b; return 1;} return 0; }
template<class T> inline bool chmin(T &a, T b) { if(b < a) {a = b; return 1;} return 0; }
using namespace std;
using ll = long long;

// For proof, see https://mzhang2021.github.io/cp-blog/berlekamp-massey/#proofs
template<ll P>
class BerlekampMassey {
	private:
		static ll mPow(ll a, ll b) { return ((b & 1) ? (a * mPow(a, b ^ 1) % P) : (b ? mPow(a*a % P, b >> 1) : 1)); }
		static void mDec(ll& a, ll b) { a = (a >= b ? a - b : a + P - b); }
		static void polyMulMod(vector<ll>& a, vector<ll>& b, const vector<ll>& c) {
			int n = (int)c.size() - 1;
			for (int i = 2*n-2; i >= 0; --i) {
				ll v = 0;
				for (int x = max(0, i+1-n); x < min(n, i + 1); ++x) v = (v + a[x] * b[i-x]) % P;
				a[i] = v;
			}
			for (int i = 2*n-2; i >= n; --i) {
				for (int j = n; j >= 0; --j) mDec(a[i-j], c[j] * a[i] % P);
			}
		}
		vector<ll> nxt, rec, old, seq;
		int t = 0, old_t = 0, old_i = -1;
		ll old_d = 1;
	public:
		// Given a sequence seq[0], ..., seq[n-1] \in [0, P), finds the minimum t and associated rec[0], ..., rec[t] \in [0, P) s.t.
		//	1. rec[0] = 1 (mod P)
		// 	2. \sum_{j = 0}^{t} rec[j] seq[i - j] = 0 (mod P) for every i \in [t, n)
		// Time complexity: O(nt)
		BerlekampMassey(const vector<ll>& s) : nxt(s.size() + 1, 0), rec(s.size() + 1, 0), old(s.size() + 1, 0), seq(s) {
			rec[0] = 1, old[0] = 1;
			for (int i = 0; i < seq.size(); ++i) {
				ll d = s[i];
				for (int j = 1; j <= t; ++j) d = (d + rec[j] * seq[i-j]) % P;
				if (d == 0) continue;

				ll mult = d * mPow(old_d, P-2) % P;
				for (int j = 0; j <= t; ++j) nxt[j] = rec[j];
				for (int j = 0; j <= old_t; ++j) mDec(nxt[j + i - old_i], old[j] * mult % P);
				
				if (2*t <= i) {
					old_i = i, old_d = d, old_t = t;
					t = i + 1 - t;
					swap(old, rec);
				}
				swap(rec, nxt);
			}
			rec.resize(t + 1, 0);
		}
		// Returns seq[k], assuming \sum_{j = 0}^{t} rec[j] seq[i - j] = 0 (mod P) holds for i >= n
		// Time complexity: O(t^2 log k)
		ll kthTerm(ll k) const {
			if (t == 1) return seq[0] * mPow((P - rec[1]) % P, k) % P;

			vector<ll> cur(2*(t+1), 0), mult(2*(t+1), 0);
			cur[0] = 1, mult[1] = 1;
			for (; k > 0; k >>= 1) {
				if (k & 1) polyMulMod(cur, mult, rec);
				polyMulMod(mult, mult, rec);
			}
			ll res = 0;
			for (int i = 0; i < t; ++i) res = (res + cur[i] * seq[i]) % P;
			return res;
		}
		vector<ll> getRec() const { return rec; }
};


template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v) 
{
	bool first = 1;
	string res = "{";
	for(const auto &x: v) 
	{
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.FI) + ", " + to_string(p.SE) + ")"; }

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) 
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if(0) puts("No effect.")
#endif

using ll = long long;
using LL = __int128;
using pii = pair<int,int>;
using vi = vector<int>;
using db = double;
using ldb = long double;

const int maxn = 2000000;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

// Time Complexity of pollard-rho is O(n^{1/4}).
// Time Complexity of factorization is also O(n^{1/4})!
inline ll mul(ll a,ll b,ll c)
{ // using __int128 is a little bit slower，
	ll s = (__int128)a * b % c;
	return s;

	// ll s = a * b - c * ll((long double)a / c * b + 0.5);
	// return s < 0 ? s + c : s;
}
ll qp(ll a,ll k,ll mod)
{
	ll res=1;
	for(;k;k>>=1,a=mul(a,a,mod)) if(k&1) res=mul(res,a,mod);
	return res;
}

bool test(ll n,int a)
{
	if(n==a) return 1;
	if(n%2==0) return 0;
	ll d = (n-1) >> __builtin_ctzll(n-1);
	ll r = qp(a,d,n);
	while(d<n-1 && r!=1 && r!=n-1) d<<=1, r=mul(r,r,n);
	return r==n-1 || d%2;
}
bool miller(ll n)
{
	if(n==2) return 1;
	vi b({2,3,5,7,11,13});
	for(auto p: b) if(test(n,p)==0) return 0;
	return 1;
}

mt19937_64 rng(19970319);
ll myrand(ll l,ll r) { return l + rng()%(r-l+1); }
ll pollard(ll n) // return some nontrivial factor of n.
{
	auto f = [&](ll x) { return ((LL)x * x + 1) % n; };
	ll x = 0, y = 0, t = 30, prd = 2;
	while(t++%40 || __gcd(prd, n)==1) 
	{   // speedup: don't take __gcd in each iteration.
		if(x==y) x = myrand(2,n-1), y = f(x);
		ll tmp = mul(prd, abs(x-y), n);
		if(tmp) prd = tmp;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}

void factorization(ll n, vector<ll> &w)
{
	if(n == 1) return;
	if(miller(n)) w.pb(n);
	else
	{
		ll x = pollard(n);
		factorization(x, w); factorization(n / x, w);
	}
}

inline void chadd(int &x, int y) { x += y; if(x >= mod) x -= mod; }

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	
	ll m; int q; cin >> m >> q;
	vector<ll> factors;
	factorization(m, factors);
	map<ll, int> cnt;
	for(auto x: factors) cnt[x]++;
	vector<int> vec;
	for(auto [x, c]: cnt) vec.pb(c);

	int d = sz(vec), N = 1 << d;
	vi div(N);
	rep(msk, 0, N - 1) 
	{
		int tmp = 1;
		rep(i, 0, d - 1) if(msk >> i & 1) tmp = 1ll * tmp * vec[i] % mod;
		div[msk] = tmp;
	}
	vi a{1}; // gives you the first terms in the recursion.

	vi A(N), B(N);
	A[N - 1] = 1;

	int k = N; // you want first k terms in the recursion.
	rep(_, 1, k)
	{
		rep(i, 0, d - 1) rep(msk, 0, N - 1) if(msk >> i & 1) chadd(A[msk], A[msk ^ (1 << i)]);
		rep(msk, 0, N - 1)
		{
			int imsk = msk ^ (N - 1);
			B[msk] = 1ll * (A[N - 1] - A[imsk] + mod) * div[msk] % mod;
		}
		rep(msk, 0, N - 1) A[msk] = B[msk];
		int tmp = 0;
		rep(msk, 0, N - 1) if(msk) chadd(tmp, A[msk]);
		a.pb(tmp);
	}
	// debug(a);

	vector<ll> tmp(a.size());
	for (int i = 0; i < a.size(); ++i) tmp[i] = a[i];

	BerlekampMassey<mod> bm(tmp);
	for (int qi = 0; qi < q; ++qi) {
		ll query_n;
		cin >> query_n;
		ll ans = ((query_n == 1) + bm.kthTerm(query_n)) % mod;
		cout << ans << '\n';
	}
	return 0;
}