#include <fstream>
using namespace std;

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

#define r 9901

int exp(int b, int e)
{
    b = b % r;
    int rez = 1;
    while (e > 0)
    {
        if (e&1)
            rez = rez * b % r;
        b = b * b % r;
        e = e>>1;
    }
    return rez;
}

int main()
{
    int a, b, d, e;
    int s = 1;
    fin >> a >> b >> d;
    for (d = 2; d*d<=a; d++)
        if (a%d == 0)
        {
            e = 0;
            while (a%d == 0)
            {
                a = a / d;
                e++;
            }
            s = 1ull*s * (exp(d, e*b+1)-1+r)%r * exp(d-1, r-2)%r;
        }
    if (a > 1)
        s = 1ull*s * (exp(a, b+1)-1+r)%r * exp(a-1, r-2)%r;
    fout << s;
    return 0;
}