令 $A = p_1^{k_1}\times p_2^{k_2}\times … \times p_n^{k_n} $

那么 $A^B = p_1^{k_1B}\times p_2^{k_2B}\times … \times p_n^{k_nB}$

由约数之和的公式可得，$A^B$ 的约数之和为： $(1 + p_1 + p_1^{2} + … + p_1^{k_1B}) \times … \times (1 + p_n + p_n ^ 2 + … + p_n ^ {k_nB})$

暴力循环计算以上式子肯定会超时，所以我们可以采用分治的思想。

我们考虑如何快速计算 $1 + p + p ^ 2 + … + p ^ n$。

首先，我们令 $1 + p + p ^ 2 + … + p ^ n = S(p, n)$

接着我们根据 $n$ 的奇偶性分两类讨论：

1. $n$ 为奇数

   $ S(p,n) = (1 + p + … + p ^ {\frac{n - 1}{2}}) + (p ^ {\frac{n + 1}{2}} + … + p ^ n) $

   $=(1 + p + … + p^{\frac{n - 1}{2}}) + p ^ {\frac{n + 1}{2}}(1 + p + … + p^{\frac{n-1}{2}})$

   $=(1 + p^{\frac{n+1}{2}})(1 + p + … + p^{\frac{n - 1}{2}})$

   $=(1 + p^{\frac{n+1}{2}})\times S(p, \frac{n - 1}{2})$

2. $n$ 为偶数

   $ S(p,n) = (1 + p + … + p^{\frac{n}{2} - 1}) + (p^{\frac{n}{2}} + … + p^n)$

   $= (1 + p + … + p^{\frac{n}{2} - 1}) + p^{\frac{n}{2}}(1 + … + p ^ {\frac{n}{2}})$

   $= (1 + p + … + p^{\frac{n}{2} - 1}) + p^{\frac{n}{2}}(1 + … + p ^ {\frac{n}{2} - 1}) + p^n$

   $= (p^{\frac{n}{2}} + 1)\times S(p, \frac{n}{2} - 1) + p^n$

由此，我们便用 $O(logn)$ 的时间计算出 $S(p,n)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int Mod = 9901;
typedef long long LL;
int a, b;

LL qmi(int a, int b) {
    a %= Mod;
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % Mod;
        b >>= 1;
        a = a * a % Mod;
    }
    return res;
}

LL work(int p, int n) {
    if (n == 0) return 1;
    if (n & 1) return (qmi(p, n + 1 >> 1) + 1) * work(p, n - 1 >> 1) % Mod;
    else return ((qmi(p, n >> 1) + 1) * work(p, (n >> 1) - 1) % Mod + qmi(p, n)) % Mod;
}

int main() {
    scanf("%d%d", &a, &b);

    LL res = 1;
    for (int i = 2; i <= a / i; i ++) {
        int cnt = 0;
        while (a % i == 0) a /= i, cnt ++;
        res = res * work(i, cnt * b) % Mod;
    }
    if (a > 1) res = res * work(a, b) % Mod;
    if (a == 0) res = 0;
    printf("%lld\n", res);
    return 0;
}