#include <cstdio>
#include <cmath>
#define MOD 9901

using namespace std;

long long lgput(long long n,long long p)
{
    if(p == 0)
        return 1;
    if(p == 1)
        return n % MOD;
    if(p & 1)
        return n*lgput((n*n)%MOD,(p-1)>>1);
    else
        return lgput((n*n)%MOD,p>>1)%MOD;
}

int main()
{
    freopen("sumdiv.in","r",stdin);
    freopen("sumdiv.out","w",stdout);
    long long a,b;
    scanf("%lld%lld",&a,&b);
    long long n = lgput(a,b);
    long long lim = (long long)sqrt((double)n);
    bool ok = false;
    long long sum = 0;
    if(lim * lim == n)
    {
        sum += lim;
        ok = true;
        sum %= MOD;
    }
    for(long long d = 1 ; d <= lim ; d++)
    {
        if(ok == true && d == lim)
            continue;
        if(n % d == 0)
        {
            sum += d;
            sum %= MOD;
            sum += n/d;
            sum %= MOD;
        }
    }
    printf("%lld",sum%MOD);
    return 0;
}