#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#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;

template<class A, class B> string to_string(const pair<A, B> &p);
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p);
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &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(const 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(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... 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 pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

/**
 * Author: Yuhao Yao
 * Date: 22-10-30
 * Description: Primality test and Fast Factorization. The $mul$ function supports $0 \le a, b < c < 7.268 \times 10^{18}$ and is a little bit faster than \_\_int128. $Pollard(n)$ gives a non-trivial factor of $n$.
 * Time: O(x ^ {1 / 4}) for pollard-rho and same for factorizing $x$.
 * Status: tested on https://judge.yosupo.jp/problem/factorize, https://qoj.ac/contest/821/problem/2574.
 */
struct Factorization {
	inline static ll mul(ll a, ll b, ll c) { /// start-hash
		ll s = a * b - c * ll((long double) a / c * b + 0.5);
		return s < 0 ? s + c : s;
	}

	static ll mPow(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;
	}

	static bool miller(ll n) {
		auto test = [&](ll n, int a) {
			if (n == a) return true;
			if (n % 2 == 0) return false;

			ll d = (n - 1) >> __builtin_ctzll(n - 1);
			ll r = mPow(a, d, n);
			while (d < n - 1 && r != 1 && r != n - 1) {
				d <<= 1;
				r = mul(r, r, n);
			}
			return r == n - 1 || d & 1;
		};

		if (n == 2) return 1;
		for (auto p: vi{2, 3, 5, 7, 11, 13}) if (test(n, p) == 0) return 0;
		return 1;
	} /// end-hash
	
	static ll pollard(ll n) { /// start-hash
		auto myrand = [&](ll a, ll b) { 
			static mt19937_64 rng{std::chrono::system_clock::now().time_since_epoch().count()};
			return uniform_int_distribution<ll>(a, b)(rng);
		};
		auto f = [&](ll x) { return ((__int128) 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);
	}

	static vector<ll> factorize(ll n) {
		vector<ll> res;
		auto dfs = [&](auto &dfs, ll x) {
			if (x == 1) return;
			if (miller(x)) res.push_back(x);
			else {
				ll d = pollard(x);
				dfs(dfs, d);
				dfs(dfs, x / d);
			}
		};
		dfs(dfs, n);
		return res;
	} /// end-hash
};

/**
 * Author: Yuhao Yao
 * Date: 23-04-14
 * Description: Modular integer with $mod \le 2^{31} - 1$. Note that there are several advantages to use this code:
   1. You do not need to keep writing $\%\, mod$;
   2. It is good to use this struct when doing Gaussian Elimination / Fast Walsh-Hadamard Transform;
   3. Sometimes the input number is greater than $mod$ and this code handles it.
  Do not write things like $mint\{1 / 3\}.pow(10)$ since $1 / 3$ simply equals $0$.
  Do not write things like $mint\{a * b\}$ where $a$ and $b$ are int since you might first have integer overflow.
 * Usage: Define the followings globally:
   const int mod = 998244353;
   using mint = MInt<mod>;
 * Status: tested on https://ac.nowcoder.com/acm/contest/33191/F.
 */
template<const unsigned &mod>
struct MInt {
	using Z = MInt;
	unsigned x; /// start-hash
	MInt(ll a = 0): x(a % mod + mod) { if (x >= mod) x -= mod; }
	explicit operator int() const { return x; }

	Z& operator +=(Z b) { x += b.x; if (x >= mod) x -= mod; return *this; }
	Z& operator -=(Z b) { x += mod - b.x; if (x >= mod) x -= mod; return *this; }
	Z& operator *=(Z b) { x = 1ll * x * b.x % mod; return *this; }
	friend Z operator +(Z a, Z b) { return a += b; }
	friend Z operator -(Z a, Z b) { return a -= b; }
	friend Z operator -(Z a) { return Z{} - a; }
	friend Z operator *(Z a, Z b) { return a *= b; }
	/// end-hash

	// the followings are for ntt and polynomials.
	Z pow(ll k) const { /// start-hash
		Z res = 1, a = *this;
		for (; k; k >>= 1, a = a * a) if (k & 1) res = res * a;
		return res;
	}
	Z& operator /=(Z b) {
		assert(b.x != 0);
		return *this *= b.pow(mod - 2);
	}
	friend Z operator /(Z a, Z b) { return a /= b; }
	friend bool operator ==(Z a, Z b) { return a.x == b.x; }
	friend bool operator <(Z a, Z b) { return a.x < b.x; }

	static unsigned getMod() { return mod; } // ntt need this.
	/// end-hash

	friend istream &operator >>(istream &is, Z &a) {
		ll v; is >> v;
		a = v;
		return is;
	}
	friend string to_string(Z a) { return to_string(a.x); }
};

/**
 * Author: Yuhao Yao
 * Date: 23-05-09
 * Description: Berlekamp-Massey Algorithm finds the shortest linear recurrence of sequence $a$. Given $a_0, \ldots, a_{n - 1}$, it finds shortest sequence $c_0, \ldots, c_{m - 1}$ such that $c_0 = 1$ and $\sum_{j = 0}^{m - 1} c_j \cdot a_{i - j} = 0$ for all $i \ge m - 1$.
 * Usage: BerlekampMMassey bm(vector<mint>{1, 2, 4});
   vector<mint> cs = bm.getRec();
 * TIme: $O(nm)$ for finding sequence $c$ where $m$ is the length of $c$.
 * Status: tested on https://judge.yosupo.jp/problem/find_linear_recurrence.
 */
template<class T>
class BerlekampMassey {
	vector<T> as, cs;
public:
	BerlekampMassey(const vector<T> &as): as(as), cs{1} {
		vector<T> old_cs{1};
		int old_i = -1;
		T old_delta = 1;
		rep(i, 0, sz(as) - 1) {
			T delta = 0;
			rep(j, 0, sz(cs) - 1) delta += cs[j] * as[i - j];
			if (delta == 0) continue;

			T mult = delta / old_delta;
			vector<T> ncs = cs;
			ncs.resize(max(sz(cs), i - old_i + sz(old_cs)));
			rep(j, 0, sz(old_cs) - 1) ncs[j + i - old_i] -= old_cs[j] * mult;

			if (i - sz(cs) > old_i - sz(old_cs)) {
				old_i = i; 
				old_delta = delta;
				swap(old_cs, cs);
			}
			swap(cs, ncs);
		}
	}
	vector<T> getRec() { return cs; }
	
	T kthTerm(ll k) {
		auto polymul = [&](const vector<T> &as, const vector<T> &bs) {
			vector<T> res(sz(as) + sz(bs) - 1);
			rep(i, 0, sz(as) - 1) rep(j, 0, sz(bs) - 1) res[i + j] += as[i] * bs[j];
			if (sz(res) < sz(cs)) return res;
			
			revrep(i, sz(cs) - 1, sz(res) - 1) {
				revrep(j, 0, sz(cs) - 1) res[i - j] -= cs[j] * res[i];
			}
			res.resize(sz(cs) - 1);
			return res;
		};

		vector<T> cur{1}, mult{0, 1};
		for (; k > 0; k >>= 1) {
			if (k & 1) cur = move(polymul(cur, mult));
			mult = move(polymul(mult, mult));
		}
		T res = 0;
		rep(i, 0, sz(cs) - 1) res += cur[i] * as[i];
		return res;
	}
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	static const unsigned mod = 1e9 + 7;
	using mint = MInt<mod>;

	ll m; int q; cin >> m >> q;
	vector<ll> factors = Factorization::factorize(m);

	map<ll, int> cnt;
	for (auto x: factors) cnt[x]++;
	vi vec;
	for (auto [x, c]: cnt) vec.push_back(c);

	int d = sz(vec), tot = 1 << d;
	vector<mint> div(tot);
	rep(msk, 0, tot - 1) {
		mint tmp = 1;
		rep(i, 0, d - 1) if (msk >> i & 1) tmp *= vec[i];
		div[msk] = tmp;
	}
	vector<mint> init{1}; // gives you the first terms in the recursion.

	vector<mint> as(tot);
	as[tot - 1] = 1;

	int k = tot + 100; // you want first k terms in the recursion.
	rep(_, 1, k) {
		rep(i, 0, d - 1) rep(msk, 0, tot - 1) if (msk >> i & 1) as[msk] += as[msk ^ (1 << i)];
		vector<mint> bs(tot);
		rep(msk, 0, tot - 1) {
			int imsk = msk ^ (tot- 1);
			bs[msk] = (as[tot - 1] - as[imsk]) * div[msk];
		}
		swap(as, bs);
		mint tmp = 0;
		rep(msk, 0, tot - 1) if (msk) tmp += as[msk];
		init.push_back(tmp);
	}

	BerlekampMassey bm(init);
	while (q--) {
		ll n;
		cin >> n;
		mint ans = bm.kthTerm(n);
		if (n == 1) ans += 1;
		printf("%d\n", (int) ans);
	}
	return 0;
}