7965. 퀴즈

#include<cstdio>

int t;
unsigned long long d[1000001];

unsigned long long z(unsigned long long n, unsigned long long exp) {
	
	unsigned long long ans = 1;
	while (exp) {
		if (exp & 1) {
			ans = (ans * n);
			ans = ans % 1000000007;
		}
		n *= n;
		n %= 1000000007;
		exp >>= 1;
	}
	return ans % 1000000007;
}//고속 제곱 함수

int main() {
	scanf("%d", &t);
	int n = 1;
	d[1] = 1;
	for (unsigned long long i = 2; i <= 1000000; i++) {
		d[i] = (d[i - 1] % 1000000007 + z(i, i) % 1000000007) % 1000000007;
	}



	while (t--) {
		int x;
		scanf("%d", &x);
		
		
		
		
		printf("#%d %lld\n", n, d[x]);
		n++;
	}
	return 0;
}

고속 제곱함수 어떻게 해야될지 너무막막해서 그냥한번 찾아서 풀어본문제