这只是个结论题
我们都知道对于n个点的图，可以构成的无根树种类是$n^{n-2}$，既然是有根图，那就规定一个n，答案就是$n^{n-1}$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
long long mod=1000000009;
int t;
int n;
long long qp(long long bas,long long mi){
    long long ans=1;
    while(mi){
        if(mi&1){
            ans*=bas;
            ans%=mod;
        }
        bas*=bas;
        bas%=mod;
        mi>>=1;
    }
    return ans;
}
int main(){
    read(t);
    while(t--){
        read(n);
        cout<<qp(n,n-1)<<endl;;
    }
    return 0;
}