#include <bits/stdc++.h>
#define maxN 1000002
#define mod 9901LL
#define ll long long
using namespace std;
int n, t, prime[maxN / 5];
bool w[maxN];
ll p[maxN / 5];
ll d[maxN];
ll p1, p2, x, b;
ll lgput(ll a, ll b)
{
    if (b == 0LL)
        return 1LL;
    if (b == 1)
        return a;
    if (b % 2)
        return (1LL * a * lgput(a, b - 1)) % mod;
    else
    {
        ll aux = lgput(a, b / 2);
        return (1LL * aux * aux) % mod;
    }
}
void prime_no()
{
    int i, j;
    for (i = 2; i <= maxN; ++ i)
        if (!w[i])
        {
            prime[++ prime[0]] = i;
            if (1LL * i * i > maxN)
                continue;
            for (j = 1LL * i * i; j <= maxN; j += i)
                w[j] = 1;
        }
}
ll invm(ll x)
{
    ll y = lgput(x, mod - 2);
    return y;

}
void read()
{
    scanf("%lld %lld", &x, &b);
}
void get_sd()
{
    int i;
    ll q = 1LL;
    p2 = 1LL;
    for (i = 1; i <= p[0]; ++ i)
    {
        q = lgput(p[i], (d[i] + 1)  % (mod - 1)) + (mod - 1);
        if (q > mod)
            q -= mod;
        q = 1LL * q * invm(p[i] - 1);
        p2 = (1LL * q * p2) % mod;
    }
}
void solve()
{
    int i;
    d[0] = p[0] = 0;
    for (i = 1; i <= prime[0] && prime[i] * prime[i] <= x; ++ i)
        if (x % prime[i] == 0)
        {
            p[++ p[0]] = prime[i];
            d[p[0]] = 0;
            while (x % prime[i] == 0)
            {
                x /= prime[i];
                ++ d[p[0]];
            }
            d[p[0]] = (1LL * d[p[0]] * b);
            if (x == 1)
                break;
        }
    if (x != 1)
        {p[++ p[0]] = x;
    d[p[0]] = (1LL * b) ;
    }
    get_sd();
}
void write()
{
   printf("%lld\n", p2);
}
int main()
{
    freopen("sumdiv.in", "r", stdin);
    freopen("sumdiv.out", "w", stdout);
    prime_no();
    read();
    solve();
    write();
    return 0;
}