RT，$n$ 一大就输出 inf，为什么？

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
long long t, n;
long long power(long long n, long long m){
    long long res = 1;
    while (m){
        if (m & 1){
        	res = (res * n) % mod;
		}
        n = (n * n) % mod;
        m = m >> 1;
    }
    return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--){
		cin >> n;
		cout << pow(n, n - 1) << endl;
	}
	return 0;
}