#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
inline int in() {
  char ch = getchar();
  int f = 1, x = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return f * x;
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 3000010;
long long fac[N], inv[N];
long long ksm(long long a, long long b, long long MOD = mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
void init(int n) {
  fac[0] = 1;
  for (int i = (1); i <= (int)(n); ++i) fac[i] = fac[i - 1] * i % mod;
  inv[n] = ksm(fac[n], mod - 2);
  for (int i = (n - 1); i >= (int)(0); --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
long long C(int n, int m) {
  if (m > n || m < 0) return 0;
  return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Initialization() { init(3e6 + 1); }
int n, q;
long long f[N][4];
void add(long long &x, long long y) { (x += y) %= mod; }
void solve(int CaseNum) {
  n = in(), q = in();
  for (int i = (1); i <= (int)(n); ++i) {
    add(f[1][1], 3 * i - 2);
    add(f[1][2], 3 * i - 1);
    add(f[1][3], 3 * i);
  }
  long long inv3 = ksm(3, mod - 2);
  for (int i = (2); i <= (int)(3 * n); ++i) {
    f[i][3] = (2 * f[i - 1][2] + C(3 * n + 1, i + 1) + f[i - 1][1]) % mod *
              inv3 % mod;
    f[i][2] = (f[i][3] - f[i - 1][2] + mod) % mod;
    f[i][1] = (C(3 * n + 1, i + 1) - f[i][3] - f[i][2] + mod + mod) % mod;
  }
  for (int i = (1); i <= (int)(q); ++i) {
    int x = in();
    printf("%lld\n", (f[x][3] % mod + mod) % mod);
  }
}
int main() {
  int T = 1;
  Initialization();
  for (int _ = (1); _ <= (int)(T); ++_) solve(_);
  return 0;
}
