#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
typedef long long ll;
ll ksm(ll x,int y,int mo){
    ll an=1;
    while(y){
        if (y&1) an=an*x%mo;
        x=x*x%mo; y>>=1;
    }
    return an;
}
const int mo=1e9+9;
int main(){
    int _,n; scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        ll zs=ksm(2,n,mo-1)+mo-2; //zs=zs%(mo-1);
        //cout<<zs<<endl;
        ll s=ksm(2,zs,mo); //cout<<s<<endl;
        ll fz=s-ksm(2,n,mo)+1; fz=(fz+mo)%mo;
        printf("%lld\n",fz*ksm(s,mo-2,mo)%mo);
    }
    return 0;
}