#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e6;
const ll mod = 1e9 + 7;
ll fact[3 * maxn + 10];
ll inv_fact[3 * maxn + 10];
ll qpow(ll a, ll p) {
  ll res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod;
    p >>= 1;
  }
  return res;
}
ll binom(int n, int m) {
  if (m > n) return 0;
  return fact[n] * inv_fact[m] % mod * inv_fact[n - m] % mod;
}
void init() {
  fact[0] = 1;
  for (int i = 1; i <= 3 * maxn; i++) fact[i] = (fact[i - 1] * i) % mod;
  inv_fact[3 * maxn] = qpow(fact[3 * maxn], mod - 2);
  for (int i = 3 * maxn - 1; i >= 0; i--)
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
}
ll n;
ll dp[3 * maxn + 5][3];
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  init();
  ll inv3 = qpow(3, mod - 2);
  cin >> n;
  dp[0][0] = dp[0][1] = dp[0][2] = n;
  for (ll i = 1; i <= 3 * n; i++) {
    dp[i][0] = (binom(3 * n, i + 1) + mod -
                (2 * dp[i - 1][0] % mod + dp[i - 1][1]) % mod) %
               mod * inv3 % mod;
    dp[i][1] = (dp[i][0] + dp[i - 1][0]) % mod;
    dp[i][2] = (dp[i][1] + dp[i - 1][1]) % mod;
  }
  ll q;
  cin >> q;
  while (q--) {
    ll x;
    cin >> x;
    cout << (dp[x][0] + binom(3 * n, x)) % mod << "\n";
  }
  return 0;
}
