#include <fstream>
using namespace std;

ifstream cin ("sumdiv.in");
ofstream cout ("sumdiv.out");

const int mod = 9901;
int invers[9901];

int Invers (const int valoare)
{
    return valoare <= 1 ? 1 : mod - (mod / valoare) * Invers(mod % valoare) % mod;
}

int Exponentiere (int baza , long long exponent)
{
    int rezultat = 1;
    while (exponent)
    {
        if (exponent & 1)
            (rezultat *= baza) %= mod;

        (baza *= baza) %= mod;
        exponent >>= 1;
    }

    return rezultat;
}

int main ()
{
    int valoare , factor_exponent;
    cin >> valoare >> factor_exponent;

    int suma = 0;
    for (int factor = 2 ; factor * factor <= valoare ; factor++)
        if (valoare % factor == 0)
        {
            int exponent = 0;
            while (valoare % factor == 0) {
                valoare /= factor;
                exponent++;
            }

            (suma += (Exponentiere(factor , 1LL * exponent * factor_exponent + 1) + mod - 1) % mod * ((factor - 1) % mod == 0 ? 0 : Invers(factor - 1)) % mod) %= mod;
        }

    if (valoare > 1)
        (suma += (Exponentiere(valoare , factor_exponent + 1) + mod - 1) % mod * ((valoare - 1) % mod == 0 ? 0 : Invers(valoare - 1)) % mod) %= mod;

    cout << suma;
    cout.close(); cin.close();
    return 0;
}