#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)
{
    long long d = 1;
    for( ; b ; b>>=1)
    {
		if( b & 1)
			d = ( d * a) % MOD;
		a = (a * a ) % 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;
}