#include <bits/stdc++.h>
using namespace std;
const long long N = 3000020, MOD = 1e9 + 7;
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
long long n, m, q, Inv, fac[N], inv[N], f[N][3];
long long mul(long long B, long long K) {
  long long base = B, res = 1, h = K;
  while (h) {
    if (h & 1) res = res * base % MOD;
    h >>= 1, base = base * base % MOD;
  }
  return res;
}
long long c(long long x, long long y) {
  return (fac[x] * inv[y] % MOD) * inv[x - y] % MOD;
}
signed main() {
  fac[0] = 1;
  for (long long i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;
  inv[N - 1] = mul(fac[N - 1], MOD - 2);
  for (long long i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
  Inv = mul(3, MOD - 2);
  n = read(), q = read();
  f[0][0] = f[0][1] = f[0][2] = n + 1;
  for (long long i = 1; i < N; i++) {
    f[i][0] = (c(3 * n + 3, i + 1) - 2 * f[i - 1][0] - f[i - 1][1]) * Inv % MOD;
    f[i][1] = (f[i][0] + f[i - 1][0]) % MOD;
    f[i][2] = (f[i][0] + f[i - 1][1]) % MOD;
  }
  for (long long i = 1; i <= q; i++) {
    m = read();
    printf("%lld\n", (f[m][0] + MOD) % MOD);
  }
  return 0;
}
