#include <fstream>
#include <cmath>
#define MOD 9901

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;
    a%=MOD;
    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;
        d = d % MOD;
    }
    return d;

}


int main()
{
    long long n, k, div [1001], e[1001], x = 0, sum = 1, aux;

    fin>>n>>k;

    for(int i=2;i*i<n;i++)
    {
        if(n % i == 0)
        {
            div[++x] = i;
            e[x] = 1;
            while( n % i == 0)
            {
                e[x]++;
                n /= i;
            }
            e[x] *= k;
        }
    }
    if( n )
    {
        div[++x] = n;
        e[x] = k;
    }
    for(int i=1; i <= x; i++)
    {

        if(div[i] % MOD == 1)
            aux = e[i] + 1;
        else
        {
            aux = (putere(div[i], e[i])*div[i] + MOD - 1  ) % MOD;
            aux = (putere(div[i]-1, 9899)* aux) % MOD;
        }
        sum = (sum * aux) % MOD;

    }

    fout<<sum<<'\n';

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