#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define mod 9901
FILE*f=fopen("sumdiv.in","r");
FILE*g=fopen("sumdiv.out","w");
long long a,b,P=1;
long putere(long a, long b)
        {
        long rez=1,x;
        x=a;
        while(b)
             {
              if(b%2==0) { a=(a*a)%mod; b=b/2; }
              else { rez=(rez*a)%mod; b--; }
             }
        if(rez==0&&x%mod==0) rez=x;
        return rez;
        }

void solve()
        {
         long long i,r,sol,p;
         for(i=2;i*i<=a;++i)
             {
              for(r=0;a%i==0;a=a/i,++r);
              if(r)
                    {
                     sol=(putere(i-1,mod-2)*(putere(i,b*r+1)-1))%mod;
                     P=(P*sol)%mod;
                    }
             }

        if(a>1)
             {
              sol=(putere(a-1,mod-2)*(putere(a,b+1)-1))%mod;
              P=(P*sol)%mod;
              }

       fprintf(g,"%lld\n",P);
       }
int main()
       {
       //fscanf(f,"%lld %lld",&a,&b);
       a=9901; b=1;
       solve();
       return 0;
       }
      //3*5 => 3^2 * 5^2  1+3+9 * 1+5+25