/*思路是 求因子和，把A分解成p^k*p2^k2.....然后求解因子和为
s=（p^0...+p^(B*k)）*.....;
其次，s%9901=（1-p^(K*B+1)）/（1-P）mod 9901；
我没借同于式，就解了个1-p^(K*B+1）MOD 9901；
然后再1~9901 去搜索 x 使得（1-P）*x mod=1-p^(K*B+1）MOD 9901；*/


//代码如下

#include <iostream>
#define MODE 9901
using namespace std;
__int64 Model(__int64 p,__int64 sum);
__int64 Decompose(__int64 A,__int64 B);
__int64 Simp(__int64 p,__int64 sum,__int64 B );
__int64 Ans(__int64 m,__int64 p);
__int64 Decompose(__int64 A,__int64 B)//因式分解
{
    int M=1,m;
    for(int i=2;i<=A;i++)
    {
        __int64 sum=0;
        while(A%i==0)
        {
            sum++;
            A/=i;
        }
        int m=Simp(i,sum,B);//化简用的
        M=(M*m)%MODE;
    }
    return M;
}
__int64 Simp(__int64 p,__int64 sum,__int64 B )//化简
{
    if(sum==0)
       return 1;
    else
    {
        p%=MODE;
        sum=sum*B+1;
        int m=Model(p,sum);//求1-p^(K*B+1）MOD 9901
       if(m!=0)
        return Ans(m,p);
      else
     return 1;
    }
}
__int64 Model(__int64 p,__int64 sum)//求1-p^(K*B+1）MOD 9901
{
   int i=0,M=1;
   int a[64],ans[64]={p};

   while(sum)
   {
        a[i]=sum%2;
        sum/=2;
        i++;
    }
    if(a[0]==1) M=p;
    for(int j=1;j<i;j++)
    {
        ans[j]=(ans[j-1]*ans[j-1])%MODE;
        if(a[j]==1)
        M=(M*ans[j])%MODE;
    }
    return M-1;
}
__int64 Ans(__int64 m,__int64 p)//搜说 x
{
    for(int i=1;i<MODE;i++)
    {
        if( ((p-1)*i)%MODE==m )
        {  return i ;}
    }
}
int main ()
{
   int A,B;
   while(cin>>A>>B)
   {
       if(A%MODE==0)
       cout<<1<<endl;
       else if(A%MODE==1)
       cout<<1+B<<endl;
       else
       cout<<Decompose(A,B)<<endl;
   }
}