[题解]luogu_P4430猴子打架

#include<bits/stdc++.h>
using namespace std;
const int mod=9999991;
int n;
long long ans=1;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-2;i++)ans=(ans*n)%mod;
    for(int i=1;i<=n-1;i++)ans=(ans*i)%mod;
    printf("%lld\n",ans);
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+9;
ll n;
inline ll qpow(ll a,ll b){
    ll base=a,ans=1;
    while(b){
        if(b&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return ans%mod;
}
int main(){int T;
    scanf("%d",&T);
    for(int pp=1;pp<=T;pp++){
        scanf("%d",&n);
        printf("%lld\n",qpow(n,n-1));
    }
}