#include <iostream>
#include <fstream>
#define ll long long
#define P 9901
using namespace std;
ifstream f("sumdiv.in");
ofstream g("sumdiv.out");
const int maxn=10005;
int v[5001],k,A,B;
bool prim[maxn+1];

void ciur()
{
    k=0;
    for(int i=4; i<=maxn; i+=2)
        prim[i]=1;
    for(int i=3; i<=maxn; i+=2)
        if(!prim[i])
        {
            for(int j=2*i; j<=maxn; j+=i)
                prim[j]=1;
        }
    v[++k]=2;
    for(int i=3; i<=maxn; i+=2)
        if(prim[i]==0)
        {
            k++;
            v[k]=i;
        }
}
ll pow(ll b,ll p)
{
    if(p==0)
        return 1;
    if(p==1)
        return b;
    ll n=1,pB=b;
    while(p)
    {
        if(p%2==1)
        {
            n=(n*pB)%P;
            p--;
        }
        else
        {
            p/=2;
            pB=(pB*pB)%P;
        }
    }
    return n;
}

void solve(int n, int b)
{
    ll sd=1;
    int i=1;
    while(i<=k && 1LL*v[i]*v[i]<=n)
    {
        if(n%v[i] || v[i]==P)
        {
            i++;
            continue;
        }
        ll crt=0;
        while(n%v[i]==0)
        {
            crt++;
            n/=v[i];
        }
        crt*=b;
        ll nr=(1LL*pow(v[i],crt+1)-1)%P;
        sd=(((sd*nr)%P)*pow(v[i]-1,P-2)%P)%P;
        i++;
    }
    if(n>1)
    {
        ll nr=(1LL*pow(n,b+1)-1)%P;
        sd=(((sd*nr)%P)*pow(n-1,P-2)%P)%P;
    }
    g<<sd<<'\n';
}
int main()
{
    f>>A>>B;
    solve(A,B);
}