#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() { return abs((int)mt()); }
inline int mrand(int k) { return abs((int)mt()) % k; }
struct Polynomial {
  static const int maxn = 1e7 + 5;
  static const int limit = 1e3;
  static const int mod = (int)1e9 + 7;
  int deg;
  vector<int> cof;
  Polynomial(int deg = 0) : deg(deg) { cof.resize(deg + 1, 0); }
  void init(int deg) {
    this->deg = deg;
    cof.resize(deg + 1, 0);
    for (int i = 0; i <= deg; i++) {
      cof[i] = 0;
    }
  }
  void shrink() { cof.resize(deg + 1); }
  friend Polynomial product(Polynomial f, Polynomial g) {
    Polynomial h(f.deg + g.deg);
    for (int i = 0; i <= f.deg; i++) {
      for (int j = 0; j <= g.deg; j++) {
        h.cof[i + j] = (h.cof[i + j] + (long long)f.cof[i] * g.cof[j]) % mod;
      }
    }
    return h;
  }
  friend Polynomial quotient(Polynomial f, Polynomial g) {
    Polynomial q(f.deg - g.deg);
    for (int i = q.deg; i >= 0; i--) {
      q.cof[i] =
          (long long)f.cof[g.deg + i] * fpow(g.cof[g.deg], mod - 2, mod) % mod;
      for (int j = g.deg; j >= 0; j--) {
        f.cof[i + j] =
            (f.cof[i + j] - (long long)q.cof[i] * g.cof[j] % mod + mod) % mod;
      }
    }
    return q;
  }
  friend Polynomial remainder(Polynomial f, Polynomial g) {
    if (f.deg < g.deg) return f;
    for (int i = f.deg - g.deg; i >= 0; i--) {
      int c =
          (long long)f.cof[g.deg + i] * fpow(g.cof[g.deg], mod - 2, mod) % mod;
      for (int j = g.deg; j >= 0; j--) {
        f.cof[i + j] =
            (f.cof[i + j] - (long long)c * g.cof[j] % mod + mod) % mod;
      }
    }
    f.deg = g.deg - 1;
    while (!f.cof[f.deg]) f.deg--;
    f.deg = max(f.deg, 0);
    f.shrink();
    return f;
  }
  friend Polynomial gcd(Polynomial f, Polynomial g) {
    if (!g.deg && !g.cof[0]) return f;
    return gcd(g, remainder(f, g));
  }
  friend vector<int> findroots(Polynomial f) {
    srand(time(NULL));
    vector<int> res;
    if (f.deg == 1) {
      int root =
          (mod - (long long)f.cof[0] * fpow(f.cof[1], mod - 2, mod) % mod) %
          mod;
      res.push_back(root);
      return res;
    }
    int it = 0;
    while (it++ < limit) {
      int d = rand() % mod;
      Polynomial a(1), r(0);
      a.cof[1] = 1, a.cof[0] = d;
      r.cof[0] = 1;
      int k = (mod - 1) >> 1;
      while (k) {
        if (k & 1) r = remainder(product(r, a), f);
        a = remainder(product(a, a), f);
        k >>= 1;
      }
      r.cof[0]--;
      a = gcd(f, r);
      if (a.deg > 0 && a.deg < f.deg) {
        r = quotient(f, a);
        res = findroots(a);
        vector<int> res2 = findroots(r);
        res.insert(res.end(), res2.begin(), res2.end());
        it = 0;
        return res;
      }
    }
    return res;
  }
};
void chemthan() {
  int n, q;
  cin >> n >> q;
  vector<int> fac(3 * n + 555, 1);
  for (int i = (1); i < (int((fac).size())); ++i) fac[i] = mult(fac[i - 1], i);
  vector<int> inv_fac(int((fac).size()));
  for (int i = (0); i < (int((fac).size())); ++i) inv_fac[i] = inv(fac[i]);
  auto binom = [&](int n, int k) {
    return mult(fac[n], mult(inv_fac[k], inv_fac[n - k]));
  };
  Polynomial a;
  Polynomial b;
  a.init(3 * (n + 1));
  b.init(3);
  for (int i = (0); i < (int((a.cof).size())); ++i) {
    a.cof[i] = binom(3 * (n + 1), i);
  }
  submod(a.cof[0], 1);
  for (int i = (0); i < (int((b.cof).size())); ++i) {
    b.cof[i] = binom(3, i);
  }
  submod(b.cof[0], 1);
  Polynomial res = quotient(a, b);
  while (q--) {
    int x;
    cin >> x;
    cout << res.cof[x] << "\n";
  }
}
int32_t main(int32_t argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Three little pigs from all over the world are meeting for a convention! Every minute, a triple of 3 new pigs arrives on the convention floor. After the n-th minute, the convention ends.

The big bad wolf has learned about this convention, and he has an attack plan. At some minute in the convention, he will arrive and eat exactly x pigs. Then he will get away.

The wolf wants Gregor to help him figure out the number of possible attack plans that involve eating exactly x pigs for various values of x (1 ≤ x ≤ 3n). Two attack plans are considered different, if they occur at different times or if the sets of little pigs to eat are different.

Note that all queries are independent, that is, the wolf does not eat the little pigs, he only makes plans!

Input

The first line of input contains two integers n and q (1 ≤ n ≤ 10^6, 1 ≤ q ≤ 2⋅ 10^5), the number of minutes the convention lasts and the number of queries the wolf asks.

Each of the next q lines contains a single integer x_i (1 ≤ x_i ≤ 3n), the number of pigs the wolf will eat in the i-th query.

Output

You should print q lines, with line i representing the number of attack plans if the wolf wants to eat x_i pigs. Since each query answer can be large, output each answer modulo 10^9+7.

Examples

Input


2 3
1
5
6


Output


9
6
1


Input


5 4
2
4
6
8


Output


225
2001
6014
6939

Note

In the example test, n=2. Thus, there are 3 pigs at minute 1, and 6 pigs at minute 2. There are three queries: x=1, x=5, and x=6.

If the wolf wants to eat 1 pig, he can do so in 3+6=9 possible attack plans, depending on whether he arrives at minute 1 or 2.

If the wolf wants to eat 5 pigs, the wolf cannot arrive at minute 1, since there aren't enough pigs at that time. Therefore, the wolf has to arrive at minute 2, and there are 6 possible attack plans.

If the wolf wants to eat 6 pigs, his only plan is to arrive at the end of the convention and devour everybody.

Remember to output your answers modulo 10^9+7!

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() { return abs((int)mt()); }
inline int mrand(int k) { return abs((int)mt()) % k; }
struct Polynomial {
  static const int maxn = 1e7 + 5;
  static const int limit = 1e3;
  static const int mod = (int)1e9 + 7;
  int deg;
  vector<int> cof;
  Polynomial(int deg = 0) : deg(deg) { cof.resize(deg + 1, 0); }
  void init(int deg) {
    this->deg = deg;
    cof.resize(deg + 1, 0);
    for (int i = 0; i <= deg; i++) {
      cof[i] = 0;
    }
  }
  void shrink() { cof.resize(deg + 1); }
  friend Polynomial product(Polynomial f, Polynomial g) {
    Polynomial h(f.deg + g.deg);
    for (int i = 0; i <= f.deg; i++) {
      for (int j = 0; j <= g.deg; j++) {
        h.cof[i + j] = (h.cof[i + j] + (long long)f.cof[i] * g.cof[j]) % mod;
      }
    }
    return h;
  }
  friend Polynomial quotient(Polynomial f, Polynomial g) {
    Polynomial q(f.deg - g.deg);
    for (int i = q.deg; i >= 0; i--) {
      q.cof[i] =
          (long long)f.cof[g.deg + i] * fpow(g.cof[g.deg], mod - 2, mod) % mod;
      for (int j = g.deg; j >= 0; j--) {
        f.cof[i + j] =
            (f.cof[i + j] - (long long)q.cof[i] * g.cof[j] % mod + mod) % mod;
      }
    }
    return q;
  }
  friend Polynomial remainder(Polynomial f, Polynomial g) {
    if (f.deg < g.deg) return f;
    for (int i = f.deg - g.deg; i >= 0; i--) {
      int c =
          (long long)f.cof[g.deg + i] * fpow(g.cof[g.deg], mod - 2, mod) % mod;
      for (int j = g.deg; j >= 0; j--) {
        f.cof[i + j] =
            (f.cof[i + j] - (long long)c * g.cof[j] % mod + mod) % mod;
      }
    }
    f.deg = g.deg - 1;
    while (!f.cof[f.deg]) f.deg--;
    f.deg = max(f.deg, 0);
    f.shrink();
    return f;
  }
  friend Polynomial gcd(Polynomial f, Polynomial g) {
    if (!g.deg && !g.cof[0]) return f;
    return gcd(g, remainder(f, g));
  }
  friend vector<int> findroots(Polynomial f) {
    srand(time(NULL));
    vector<int> res;
    if (f.deg == 1) {
      int root =
          (mod - (long long)f.cof[0] * fpow(f.cof[1], mod - 2, mod) % mod) %
          mod;
      res.push_back(root);
      return res;
    }
    int it = 0;
    while (it++ < limit) {
      int d = rand() % mod;
      Polynomial a(1), r(0);
      a.cof[1] = 1, a.cof[0] = d;
      r.cof[0] = 1;
      int k = (mod - 1) >> 1;
      while (k) {
        if (k & 1) r = remainder(product(r, a), f);
        a = remainder(product(a, a), f);
        k >>= 1;
      }
      r.cof[0]--;
      a = gcd(f, r);
      if (a.deg > 0 && a.deg < f.deg) {
        r = quotient(f, a);
        res = findroots(a);
        vector<int> res2 = findroots(r);
        res.insert(res.end(), res2.begin(), res2.end());
        it = 0;
        return res;
      }
    }
    return res;
  }
};
void chemthan() {
  int n, q;
  cin >> n >> q;
  vector<int> fac(3 * n + 555, 1);
  for (int i = (1); i < (int((fac).size())); ++i) fac[i] = mult(fac[i - 1], i);
  vector<int> inv_fac(int((fac).size()));
  for (int i = (0); i < (int((fac).size())); ++i) inv_fac[i] = inv(fac[i]);
  auto binom = [&](int n, int k) {
    return mult(fac[n], mult(inv_fac[k], inv_fac[n - k]));
  };
  Polynomial a;
  Polynomial b;
  a.init(3 * (n + 1));
  b.init(3);
  for (int i = (0); i < (int((a.cof).size())); ++i) {
    a.cof[i] = binom(3 * (n + 1), i);
  }
  submod(a.cof[0], 1);
  for (int i = (0); i < (int((b.cof).size())); ++i) {
    b.cof[i] = binom(3, i);
  }
  submod(b.cof[0], 1);
  Polynomial res = quotient(a, b);
  while (q--) {
    int x;
    cin >> x;
    cout << res.cof[x] << "\n";
  }
}
int32_t main(int32_t argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```