40分：

#include<bits/stdc++.h>
using namespace std;
int ksm(int a, int b)
{
    int ans = 1, base = a;
    while(b > 0)
    {
        if(b & 1)
            ans *= base;
        ans %=1000000009;
        base *= base;
        base %=1000000009;
        b >>= 1;
    }
    return ans;
}

int main()
{
    unsigned long long t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        unsigned long long n;
        cin>>n;
        unsigned long long r=ksm(n,n-1);
        cout<<r%1000000009<<endl;
    }
}