3844번: 백준 공화국

https://www.acmicpc.net/problem/3844

#include<stdio.h>
#define mod ((int)1e9+7)
const int MAX_N = 1e7;
typedef long long ll;
bool ck[MAX_N + 1];
int n, p[MAX_N / 10], pcnt;
int pow(int x, int y) {
    int t = x, r = 1;
    for (int i = 1; i <= y; i *= 2, t = (ll)t*t%mod) if (i&y) r = (ll)r*t%mod;
    return r;
}
int main() {
    for (int i = 2; i <= MAX_N; i++) {
        if (ck[i]) continue;
        p[pcnt++] = i;
        for (int j = i; j <= MAX_N; j += i) ck[j] = 1;
    }
    for (;;) {
        scanf("%d", &n);
        if (!n) break;
        int r = 1, t;
        for (int i = 0; i<pcnt; i++) {
            t = 0;
            for (int j = n / p[i]; j; j /= p[i]) t += j;
            t -= t & 1;
            if (!t) break;
            r = (ll)r*pow(p[i], t) % mod;
        }
        printf("%d\n", r);
    }
    return 0;
}