#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long mod = 1e9 + 7;
long long n, q, fact[4000005], invfact[4000005], dp[3000005][3], inv3;
long long inv(long long a) {
  long long rez = 1;
  long long b = mod - 2;
  while (b) {
    if (b & 1) rez = (rez * a) % mod;
    b /= 2;
    a = (a * a) % mod;
  }
  return rez;
}
long long comb(long long a, long long b) {
  if (a < 0 || b < 0 || a < b) return 0;
  long long rez = (fact[a] * invfact[b]) % mod;
  rez = (rez * invfact[a - b]) % mod;
  return rez;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  fact[0] = invfact[0] = 1;
  for (long long i = 1; i <= 3 * n; i++) fact[i] = (fact[i - 1] * i) % mod;
  invfact[3 * n] = inv(fact[3 * n]);
  for (long long i = 3 * n - 1; i >= 1; i--)
    invfact[i] = (invfact[i + 1] * (i + 1)) % mod;
  dp[0][0] = dp[0][1] = dp[0][2] = n;
  inv3 = inv(3);
  for (long long x = 1; x <= 3 * n; x++) {
    long long suma = comb(3 * n, x + 1);
    long long a = dp[x - 1][0];
    long long b = dp[x - 1][1];
    long long val = suma - 2 * a - b;
    while (val < 0) val += mod;
    val = (val * inv3) % mod;
    dp[x][0] = val;
    dp[x][1] = (dp[x][0] + a) % mod;
    dp[x][2] = (dp[x][1] + b) % mod;
  }
  cin >> q;
  while (q--) {
    long long x;
    cin >> x;
    cout << (dp[x][0] + comb(3 * n, x)) % mod << '\n';
  }
  return 0;
}
