#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T read() {
  T s = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    s = s * 10 + (c ^ 48);
    c = getchar();
  }
  return s * w;
}
template <class T>
inline bool Chkmax(T& x, const T& y) {
  return x < y ? x = y, true : false;
}
template <class T>
inline bool Chkmin(T& x, const T& y) {
  return x > y ? x = y, true : false;
}
const long long maxn = 3e6 + 50;
const long long Mod = 1e9 + 7;
long long n;
long long Pow(long long x, long long y) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = 1ll * ans * x % Mod;
    y >>= 1;
    x = 1ll * x * x % Mod;
  }
  return ans;
}
long long fac[maxn], inv[maxn];
long long C(long long x, long long y) {
  if (x < y) return 0;
  return 1ll * fac[x] * inv[y] % Mod * inv[x - y] % Mod;
}
long long G(long long pos) {
  if (pos == 0)
    return 0;
  else
    return Mod - C(3 * n + 3, pos);
}
long long P[maxn];
const long long inv2 = (Mod + 1) / 2;
signed main() {
  n = read<long long>();
  fac[0] = 1;
  for (long long i = 1; i <= 3 * n + 3; i++)
    fac[i] = 1ll * fac[i - 1] * i % Mod;
  inv[3 * n + 3] = Pow(fac[3 * n + 3], Mod - 2);
  for (long long i = 3 * n + 2; i >= 0; i--)
    inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;
  P[0] = n + 1;
  P[1] = 3ll * (1ll * n * (n + 1) % Mod * inv2 % Mod) % Mod;
  long long inv3 = Pow(3, Mod - 2);
  for (long long i = 3; i <= 3 * n; i++) {
    P[i - 1] =
        1ll * ((Mod - G(i)) - 3 * P[i - 2] % Mod - P[i - 3]) % Mod * inv3 % Mod;
    P[i - 1] = (P[i - 1] + Mod) % Mod;
  }
  P[3 * n] = 1;
  long long T = read<long long>();
  while (T--) {
    long long x = read<long long>();
    printf("%d\n", P[x]);
  }
  return 0;
}
