#include using namespace std; template > T power(T a, long long n, F op = multiplies(), T e = {1}) { assert(n >= 0); T res = e; while (n) { if (n & 1) res = op(res, a); if (n >>= 1) a = op(a, a); } return res; } template struct Modular { using M = Modular; unsigned v; Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {} M operator-() const { return M() -= *this; } M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; } M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; } M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; } M& operator/=(M r) { return *this *= power(r, Mod - 2); } friend M operator+(M l, M r) { return l += r; } friend M operator-(M l, M r) { return l -= r; } friend M operator*(M l, M r) { return l *= r; } friend M operator/(M l, M r) { return l /= r; } friend bool operator==(M l, M r) { return l.v == r.v; } }; template void ntt(vector>& a, bool inverse) { static vector> dw(30), idw(30); if (dw[0] == 0) { Modular root = 2; while (power(root, (Mod - 1) / 2) == 1) root += 1; for (int i = 0; i < 30; ++i) dw[i] = -power(root, (Mod - 1) >> (i + 2)), idw[i] = 1 / dw[i]; } int n = a.size(); assert((n & (n - 1)) == 0); if (not inverse) { for (int m = n; m >>= 1; ) { Modular w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j] * w; if (x.v >= Mod) x.v -= Mod; a[i].v = x.v + y.v, a[j].v = x.v + (Mod - y.v); } w *= dw[__builtin_ctz(++k)]; } } } else { for (int m = 1; m < n; m *= 2) { Modular w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j]; a[i] = x + y, a[j].v = x.v + (Mod - y.v), a[j] *= w; } w *= idw[__builtin_ctz(++k)]; } } } auto c = 1 / Modular(inverse ? n : 1); for (auto&& e : a) e *= c; } template vector> operator*(vector> l, vector> r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1); if (min(n, m) < 30) { vector res(n + m - 1); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res[i + j] += (l[i] * r[j]).v; return {begin(res), end(res)}; } bool eq = l == r; l.resize(sz), ntt(l, false); if (eq) r = l; else r.resize(sz), ntt(r, false); for (int i = 0; i < sz; ++i) l[i] *= r[i]; ntt(l, true), l.resize(n + m - 1); return l; } constexpr long long mod = 1e9 + 7; using Mint = Modular; vector operator*(const vector& l, const vector& r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(); static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617; using Mint0 = Modular; using Mint1 = Modular; using Mint2 = Modular; vector l0(n), r0(m); vector l1(n), r1(m); vector l2(n), r2(m); for (int i = 0; i < n; ++i) l0[i] = l[i].v, l1[i] = l[i].v, l2[i] = l[i].v; for (int j = 0; j < m; ++j) r0[j] = r[j].v, r1[j] = r[j].v, r2[j] = r[j].v; l0 = l0 * r0, l1 = l1 * r1, l2 = l2 * r2; vector res(n + m - 1); static const Mint1 im0 = 1 / Mint1(mod0); static const Mint2 im1 = 1 / Mint2(mod1), im0m1 = im1 / mod0; static const Mint m0 = mod0, m0m1 = m0 * mod1; for (int i = 0; i < n + m - 1; ++i) { int y0 = l0[i].v; int y1 = (im0 * (l1[i] - y0)).v; int y2 = (im0m1 * (l2[i] - y0) - im1 * y1).v; res[i] = y0 + m0 * y1 + m0m1 * y2; } return res; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int p; cin >> p; int n = 2e6; vector a(n); for (int i = 0; i < n; ++i) { if (i < 2) { a[i] = i; } else { a[i] = p * a[i - 1] + a[i - 2]; } } a = a * a; int q; cin >> q; while (q--) { int i; cin >> i; i -= 2; cout << a[i].v << '\n'; } }