#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MOD = 1000000009;

// idea: isolate one vertex at a time.
// what is the probability that vertex has the exact same set of connections?

// operation: add it to a random point in sequence and add edges in and out randomly.

// P(same) = 1/2^(n-1) * P(same set of previous vertices are possible next time.)


// idea: each individual vertex is only bad if (A) it is chosen and (B) it is on different side

// imagine we have L vertices before, R vertices after.

// fix positions for each of them: (N choose 1 + L + R)/(N!) = 1/(X!)(N-X)!
// each then remains on the right side: (L!)(R!)/(L + R + 1)!



ll modexp(ll a, ll x) {
    ll r = 1;
    while(x) {
        if(x&1) (r *= a) %= MOD;
        (a *= a) %= MOD;
        x >>= 1;
    }
    return r;
}

ll modinv(ll x) {return modexp(x, MOD-2);}

vector<ll> facts(100001);
vector<ll> ifacts(100001);

ll nck(ll n, ll k) {
    ll r = facts[n];
    r *= ifacts[k]; r %= MOD;
    r *=ifacts[n-k]; r %= MOD;
    return r;
}

const ll MAXN = 101;

int main() {
    facts[0] = 1;
    for(ll i = 1; i < facts.size(); i++) facts[i] = facts[i-1]*i % MOD;
    ifacts.back() = modinv(facts.back());
    for(ll i = facts.size()-2; i >= 0; i--) {
        ifacts[i] = (i+1)*ifacts[i+1] % MOD;
    }

    vector<ll> anses(MAXN);
    vector<ll> bylr(MAXN);
    bylr[0]=1;

    ll one_half = modinv(2);

    anses[1]=1;

    

    for(ll i = 2; i < anses.size(); i++) {
        anses[i] = anses[i-1];
        ll goods = 0;

        goods = ((modexp(2,i)-1+MOD)%MOD)*modinv(i) %MOD;
        goods %= MOD;
        anses[i] *= goods;
        anses[i] %= MOD;

        (anses[i] *= modexp(one_half, 2*(i-1))) %= MOD;
    }

    ll T; cin >> T; while(T--) {
        ll N; cin >> N;

        ll ans = 1-anses[N] + MOD;
        ans %= MOD;
        cout << ans << "\n";
    }
    
}