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; }