40pts求调，WA on #11-15

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b;
int p[10000005], c[10000005];
int qpow(int x, int y) {
    x %= 9901, y %= 9901;
    int ans = 1;
    for (; y != 0; y >>= 1) {
        if (y & 1)
            ans *= x % 9901;
        x *= x % 9901;
    }
    return ans;
}
int sum(int p1, int c1) {
    if (c1 == 0) return 1;
    if (c1 % 2 == 1) {
        int para = 1 + qpow(p1, (c1+1)/2) % 9901;
        return para * sum(p1, (c1-1)/2) % 9901;
    }
    else
        return ((1 + qpow(p1, c1/2)) % 9901 * sum(p1, c1/2-1) % 9901 + qpow(p1, c1) % 9901) % 9901;
}

signed main() {
    cin >> a >> b;
    int m = 0;
    for (int i = 2; i <= sqrt(a); i++) {
        if (a % i == 0) {
            p[++m] = i; c[m] = 0;
            while (a % i == 0) a /= i, c[m]++;
        }
    }
    if (a > 1)
        p[++m] = a, c[m] = 1;
    int ans = 1;
    for (int i = 1; i <= m; i++)
        ans = ans % 9901 * sum(p[i], b * c[i]) % 9901;
    cout << ans % 9901 << endl;
    return 0;
}