n点无根树的选择方法是n^(n-2)
一个无根树有n个点选作根，
方法数=n^(n-2)*n=n^(n-1) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+9;

ll t,n;

ll qmi(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res*=a, res%=mod;
		a*=a, a%=mod; b>>=1;
	}
	return res;
}

int main(){
	for(cin>>t;t--;){
		cin>>n;
		cout<<qmi(n,n-1)<<endl;
	}
	return 0;
}