#include <fstream>
#include <cmath>
#define MOD 9901
#define MODULO 990100
using namespace std;

ifstream fin("sumdiv.in");
ofstream fout("sumdiv.out");


int putere(long long a, long long b)
{
        fin>>a>>b;
        long long d=1;
        long long bin[10000];
        bin[0]=0;
        while(b)
        {
            bin[++bin[0]]=b%2; b/=2;
        }
        for(int i=bin[0];i>=1;i--)
        {
            d=d*d;

            if(bin[i])
                d=d*a;
            if(d>MODULO)
                d = d % MODULO;
        }
        return d;
}


int main()
{
    int n,k;
    long long sum = 1;
    fin>>n>>k;
    for(int i=2;i<=sqrt(n*1.0);i++)
    {
        if(n%i==0)
        {
            long long exp = 0;
            while(n%i == 0)
            {
                exp++;
                n /= i;
            }
            exp*=k;
            int rez = (putere(i,exp)-1) % MOD;
            sum *=(i*rez/(i-1))+1;
            if(sum>MOD)
                sum = sum%MOD;
        }
    }
    if(n)
    {
        long long exp = k;
        int rez = (putere(n,exp)-1) % MOD;
        sum *=(n*rez/(n-1))+1;
    }
    fout<<sum<<'\n';




    fin.close();
    fout.close();
    return 0;
}