#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 = div[i] + 1;
        else
        {
            aux = (putere(div[i], e[i])*div[i] + MOD - 1  ) % MOD;
            aux = (putere(div[i]-1, 9899)* aux) % MOD;
        }
        sum *= aux;
        sum %= MOD;
    }

    fout<<sum<<'\n';

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