//upd 2020/4/29,修复了没有逆元的时候会挂的bug.
不会推式子,只会背公式.

有两个需要用到的公式:
1.算术基本定理推论:
$$n=\prod_{i=1}^k p_i^{c_i}(p_i\ is\ prime)$$
$$\sigma(n)=\sum_{d|n} d=\prod_{i=1}^k\sum_{j=0}^{c_i}p_i^j$$
$$\therefore \sigma(A^B)=\prod_{i=1}^k\sum_{j=0}^{c_i\*B}p_i^j$$
2.等比数列求和公式:
$$\sum _{i=0}^{n-1} a\*p^i=a\times \frac{p^n-1}{p-1}$$

$$而推论的\sum_{j=0}^{c_i\*B}p_i^j部分就是一个等比数列$$
直接套用等比数列求和公式,分子直接快速幂取模,分母用费马小定理求逆元即可(咦,好像又用了一个定理)
质因数分解的时间复杂度是$O(\sqrt n)$,快速幂+逆元的时间复杂度是$O(logn)$,故总时间复杂度$O(\sqrt n\times logn)$,轻松通过($10^{10}$都跑得动)

另外,若$p-1\ mod\ 9901=0$,此时不存在逆元,但此时$p\ mod\ 9901=1$,特殊处理一下就好.

/**********/
const ll mod=9901;
ll Qpow(ll a,ll p)
{
    ll res=1;
    while(p)
    {
        if(p&1)res=(res*a)%mod;
        a=(a*a)%mod;
        p>>=1;
    }
    return res;
}
ll inv(ll x)
{
    return Qpow(x,mod-2);
}
int main()
{
    ll a=read(),b=read();
    if(a==0)
    {
        printf("0");
        return 0;
    }
    if(b==0)
    {
        printf("1");
        return 0;
    }
    ll ans=1;
    for(ll i=2;i*i<=a;++i)
    {
        if(a%i)continue;
        ll p=0;
        while(a%i==0)
        {
            a/=i;
            ++p;
        }
        //printf("i=%lld p=%lld\n",i,p);
        p*=b;
        if((i-1)%mod==0)ans=(ans*(p+1))%mod;
        else ans=(ans*(Qpow(i,p+1)-1+mod)%mod*inv(i-1))%mod;
        //printf("ans=%lld\n",ans);
    }
    if(a==1)
    {
        printf("%lld",ans);
        return 0;
    }
    ll p=b;
    if((a-1)%mod==0)ans=(ans*(p+1))%mod;
    else ans=(ans*(Qpow(a,p+1)-1+mod)%mod*inv(a-1))%mod;
    printf("%lld",ans);
    return 0;
}