HDU 6758

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

// template from https://sinker.blog.luogu.org/solution-p4239

constexpr int Mod = 1000000009;
using ll=long long;

struct Z {
  static constexpr int Mod1 = 645922817, Mod2 = 897581057, Mod3 = 998244353;
  int a, b, c;

  Z(const int &x = 0) : a(x % Mod1), b(x % Mod2), c(x % Mod3) {}

  Z(const int &a, const int &b, const int &c) : a(a), b(b), c(c) {}

  Z &up() {
    a += a >> 31 & Mod1;
    b += b >> 31 & Mod2;
    c += c >> 31 & Mod3;
    return *this;
  }

  Z &operator+=(const Z &rhs) {
    a += rhs.a - Mod1;
    b += rhs.b - Mod2;
    c += rhs.c - Mod3;
    return up();
  }

  Z operator-(const Z &rhs) const { return Z(a - rhs.a, b - rhs.b, c - rhs.c).up(); }

  Z operator*(const Z &rhs) const {
    return Z(static_cast<ll>(a) * rhs.a % Mod1, static_cast<ll>(b) * rhs.b % Mod2, static_cast<ll>(c) * rhs.c % Mod3);
    return *this;
  }

  int val(const int &Mod) {
    ll _a = (b - a + Mod2) % Mod2 * 867661692ll % Mod2 * Mod1 + a;
    return ((c - _a % Mod3 + Mod3) % Mod3 * 13864533 % Mod3 * Mod1 % Mod * Mod2 + _a) % Mod;
  }
};

inline int qpow(int a, int p, int Mod, int s = 1) {
  for (; p; p >>= 1, a = static_cast<ll>(a) * a % Mod) if (p & 1) s = static_cast<ll>(s) * a % Mod;
  return s;
}

int exgcd(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

inline int _inv(const int &a) {
  int x, _;
  exgcd(a, Mod, x, _);
  return x += x >> 31 & Mod;
}

inline Z inv(const Z &rhs) {
  int x1, x2, x3, _;
  exgcd(rhs.a, Z::Mod1, x1, _);
  exgcd(rhs.b, Z::Mod2, x2, _);
  exgcd(rhs.c, Z::Mod3, x3, _);
  return Z(x1, x2, x3).up();
}

constexpr int mxlen = 1 << 20;
int r[mxlen], d;
Z w[mxlen];

void fftinit(int len) {
  int _d = (d = __builtin_ctz(len)) - 1;
  for (int i = 1; i < len; ++i) r[i] = r[i >> 1] >> 1 | (i & 1) << _d;
  Z wn(qpow(3, Z::Mod1 >> d, Z::Mod1), qpow(3, Z::Mod2 >> d, Z::Mod2), qpow(3, Z::Mod3 >> d, Z::Mod3));
  w[len >> 1] = 1;
  for (int i = (len >> 1) + 1; i < len; ++i) w[i] = w[i - 1] * wn;
  for (int i = len >> 1; --i;) w[i] = w[i << 1];
}

void dft(Z a[], int len) {
  int shift = d - __builtin_ctz(len);
  for (int i = 0; i < len; ++i) if (i < r[i] >> shift) std::swap(a[i], a[r[i] >> shift]);
  for (int l = 1; l < len; l <<= 1)
    for (int i = 0; i < len; i += l << 1)
      for (int j = 0; j < l; ++j) {
        Z tmp(a[i + j + l] * w[j + l]);
        a[i + j + l] = a[i + j] - tmp;
        a[i + j] += tmp;
      }
}

void idft(Z a[], int len) {
  std::reverse(a + 1, a + len);
  dft(a, len);
  Z invn(inv(len));
  for (int i = 0; i < len; ++i) a[i] = a[i] * invn;
}

void pinv(Z a[], Z b[], int n) {
  if (n == 1) return void(*b = _inv(a->val(Mod)));
  pinv(a, b, (n + 1) >> 1);
  int len = 1;
  while (len <= n * 3 / 2) len <<= 1;
  static Z c[mxlen], d[mxlen];
  __builtin_memcpy(c, a, sizeof(Z) * n);
  __builtin_memcpy(d, b, sizeof(Z) * n);
  for (int i = n; i < len; ++i) c[i] = d[i] = 0;
  dft(c, len);
  dft(d, len);
  for (int i = 0; i < len; ++i) c[i] = c[i] * d[i];
  idft(c, len);
  for (int i = 0; i < len; ++i) c[i] = Mod - c[i].val(Mod);
  dft(c, len);
  for (int i = 0; i < len; ++i) c[i] = c[i] * d[i];
  idft(c, len);
  for (int i = (n + 1) >> 1; i < n; ++i) b[i] = c[i].val(Mod);
}

Z A[mxlen], B[mxlen];
int Bernoulli[mxlen];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  {
    int n = 400001;
    int x = 1;
    for (int i = 0; i < n; ++i) {
      A[i] = x;
      x = x * (ll) qpow(i + 2, Mod - 2, Mod) % Mod;
    }
    int len = 1;
    while (len <= n * 3 / 2) len <<= 1;
    fftinit(len);
    pinv(A, B, n);
    int fac = 1;
    for (int i = 0; i < n; ++i) {
      Bernoulli[i] = B[i].val(Mod) * (ll)fac % Mod;
      fac = fac * (1LL + i) % Mod;
    }
  }

  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    int ans = (Mod - 2 * n) * (ll)Bernoulli[4 * n] % Mod * qpow(Bernoulli[2 * n], Mod - 3, Mod) % Mod;
    cout << ans << '\n';
  }

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}