WA #11 #12 88pts 逆元

#include <bits/stdc++.h>

#define MOD 9901

using T = long long;

#define int T 

T ksm(T a, T p) {
    T res = 1;
    while(p)
    {
        if(p & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return  res % MOD;
}

int p[1145], n = 0;
int c[1145];
T A, B;

int f(int k) {
    return (ksm(p[k], B * c[k] + 1) - 1 + MOD) % MOD * ksm(p[k] - 1, MOD - 2) % MOD;
}

signed main() {
    scanf("%lld %lld", &A, &B);
    if(A == 0) {
        puts("0");
        return 0;
    }
    if(B == 0) {
        puts("1");
        return 0;
    }
    for(int i = 2; i * i <= A; i++)
    {
        if(A % i == 0) {
            p[++n] = i;
            while(A % i == 0)
                c[n]++, A /= i;
        }
    }
    if(A > 1)
        p[++n] = A, c[n]++;
    int ans = 1;
    for(int i = 1; i <= n; i++)
        ans = ans * f(i) % MOD;
    printf("%lld", ans);
    return 0;
}