#include <bits/stdc++.h>
template <class T>
void read(T &x) {
  x = 0;
  char f = 0, c = getc(stdin);
  while (c < '0' || c > '9') f ^= (c == '-'), c = getc(stdin);
  while (c >= '0' && c <= '9') x = x * 10 + (c & 15), c = getc(stdin);
  f && (x = -x);
}
int Max(int a, int b) { return a > b ? a : b; }
long long Min(long long a, long long b) { return a < b ? a : b; }
int Abs(int a) { return a < 0 ? -a : a; }
long long sqr(int a) { return (long long)a * a; }
int qpow(int a, int b) {
  if (b < 0) return 0;
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1ll * a * ans % 1000000007;
    a = 1ll * a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
int T = 1;
int n, x;
int fac[3000010], ifac[3000010], num[3000010], dp[3000010][2];
const int mod = 1000000007;
const int inv3 = (mod + 1) / 3;
int main() {
  read(n);
  dp[1][0] = (3ll * n * (n - 1) / 2) % mod;
  dp[1][1] = (dp[1][0] + n) % mod;
  num[1] = (n *= 3);
  fac[1] = fac[0] = ifac[1] = ifac[0] = 1;
  for (int i = 2; i <= n; ++i)
    fac[i] = 1ll * fac[i - 1] * i % mod,
    ifac[i] = 1ll * (mod - mod / i) * ifac[mod % i] % mod;
  for (int i = 2; i <= n; ++i) ifac[i] = 1ll * ifac[i] * ifac[i - 1] % mod;
  for (int i = 2; i <= n; ++i)
    num[i] = 1ll * fac[n] * ifac[i] % mod * ifac[n - i] % mod;
  for (int i = 2; i < n; ++i) {
    dp[i][0] = ((long long)num[i + 1] - 2ll * dp[i - 1][0] - dp[i - 1][1] +
                mod * 3ll) %
               mod * inv3 % mod;
    dp[i][1] = (dp[i][0] + dp[i - 1][0]) % mod;
  }
  read(T);
  while (T--) {
    read(x);
    printf("%d\n", (dp[x][0] + num[x]) % mod);
  }
}
