#include <fstream>
#define file "sumdiv"
#define MOD 9901
#define N 1000000

using namespace std;

ifstream fin(file".in");
ofstream fout(file".out");

typedef long long ll;

ll A,B;
ll p[N],d[N],n;

void fac_primi()
{
    if(A%2 == 0) p[++n] = 2;
    while(A%2 == 0) A/=2, ++d[n];

    ll div = 3;

    do
    {
        if(A%div == 0) p[++n] = div;
        while(A%div == 0) A/=2, ++d[n];
        if(div * div <= A) div +=2;
            else div = A;
    } while(A > 1);
}

void afis_primi()
{
    for(int i=1; i<=n; ++i)
        fout<<p[i]<<" "<<d[i]<<"\n";
}

inline ll rid_log(ll A,ll B)
{
    if(B == 1) return A;
    if(B == 0) return 1;

    ll solus = rid_log(A,B/2);

    if(B%2) return ((solus*solus)% MOD *A ) % MOD;
        else return (solus*solus)%MOD;
}

ll inv_mod(ll X)
{
    return rid_log(X,MOD-2);
}

void solve()
{
    ll sol = 1;
    for(int i=1; i<=n; ++i)
        sol = (sol*(rid_log(p[i],d[i] + 1) - 1) *inv_mod(p[i]-1)) % MOD;
    fout<<sol<<"\n";
}

int main()
{
    fin>>A>>B;

    if( A == 0)
    {
        fout<<"0\n";
        return 0;
    }
    if( B == 0)
    {
        fout<<"1\n";
        return 0;
    }

    fac_primi();

    for(int i=1; i<=n; ++i)
        d[i] *= B;

    //afis_primi();

    solve();

    fin.close();
    fout.close();
    return 0;
}