#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi pair<int,int>
#define pb push_back
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mp make_pair
#define lowbit(i) (i&(-i))
#define int long long
#define mid ((l+r)/2)
inline int read(){
    int x=0;char ch=getchar();bool f=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f)x=-x;return x;
}
const int maxn=3e5+5,mod=1e9+9;
int n,x,f[maxn],ans=0,pw[maxn],T,fac[maxn];
int g[maxn];
int Pow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*x%mod;
		}y=y/2;x=x*x%mod;
	}return res;
}
void init(int n){
	pw[0]=1;fac[0]=1;g[0]=1;
	for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2%mod,fac[i]=fac[i-1]*i%mod;
	
	for(int i=1;i<=n;i++)g[i]=g[i-1]*(pw[i]-1)%mod;
	
	for(int i=1;i<=n;i++){
		int t=g[i]*Pow(fac[i]*Pow(2,(i)*(i-1))%mod,mod-2)%mod;
		f[i]=(mod+1-t)%mod;
		//cout<<g[i]<<" "<<fac[i]<<" "<<f[i]<<" "<<Pow(2,n*(n-1))<<endl;
	}
		
}
signed main(){
    std::ios::sync_with_stdio(false);
	cin.tie(0);
	init(100);
	cin>>T;
	for(int i=1;i<=T;i++){
		cin>>x;
		printf("%lld\n",f[x]);
	}
    return 0;
}