一、
分治：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int p=9901;
const int maxn=100005;
int prime[maxn];
bool ha[maxn]={false};
int cnt=0;
void Prime(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
    return ;
}
ll pp[20];
ll e[20];
int tot=0;
ll a,b;
void only(ll n)
{
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        pp[++tot]=prime[i];
        while(n%prime[i]==0)
        {
            e[tot]++;
            n/=prime[i];
        }
    }
    if(n>1) pp[++tot]=n,e[tot]=1;
    for(int i=1;i<=tot;i++)
        e[i]*=b;
    return ;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    a%=p;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

ll sum(ll pp,ll c)
{
    if(pp==0) return 0;
    if(c==0) return 1;
    if(c&1) return ((1+mypow(pp,(c+1)/2))%p*sum(pp,(c-1)/2)%p)%p;
    else return ((1+mypow(pp,c/2))%p*sum(pp,c/2-1)%p+mypow(pp,c)%p)%p;
}

ll res(ll a,ll b)
{
    only(a);
    ll ans=1;
    for(int i=1;i<=tot;i++)
    {
       // printf("pp[i]:%lld e[i]:%lld\n",pp[i],e[i]);
        ans*=sum(pp[i],e[i])%p;
        ans%=p;
    }
    return ans;
}

int main(void)
{
    Prime();
    while(scanf("%lld%lld",&a,&b)!=EOF)
    printf("%lld\n",res(a,b));
    return 0;
}

二、求逆元法：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int p=9901;
const int maxn=100005;
int prime[maxn];
bool ha[maxn]={false};
int cnt=0;
void Prime(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
    return ;
}
ll pp[20];
ll e[20];
int tot=0;
ll a,b;
void only(ll n)
{
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        pp[++tot]=prime[i];
        while(n%prime[i]==0)
        {
            e[tot]++;
            n/=prime[i];
        }
    }
    if(n>1) pp[++tot]=n,e[tot]=1;
    for(int i=1;i<=tot;i++)
        e[i]*=b;
    return ;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    a%=p;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

ll res(ll a,ll b)
{
    only(a);
    ll ans=1;
    for(int i=1;i<=tot;i++)
    {
        if((pp[i]-1)%p==0)
        {
            ans*=(e[i]+1)%p;
            ans%=p;
            continue;
        }
        ans*=(mypow(pp[i],e[i]+1)-1+p)%p*mypow(pp[i]-1,p-2)%p;
        ans%=p;

    }
    return ans;
}

int main(void)
{
    Prime();
    while(scanf("%lld%lld",&a,&b)!=EOF)
    printf("%lld\n",res(a,b));
    return 0;
}