divizori5

#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("divizori.in");
ofstream cout ("divizori.out");
const int MOD = (int)3e6 + 17;
long long d;
int m,k,P,sol,nrPrime;
int p[100005],inv[205];
bool ciur[1000005];

int lgput(int n,int p)
{
    int sol=1,x=n;
    for(int i=0;(1<<i)<=p;++i)
    {
        if((1<<i)&p)
            sol=1LL*sol*x%MOD;
        x=1LL*x*x%MOD;
    }
    return sol;
}

int comb(int n,int k)
{
  if(n < k)
    return 0;
    int sol=1;
    for(int i=n-k+1;i<=n;++i)
        sol=1LL*sol*i%MOD;
    for(int i=2;i<=k;++i)
        sol=1LL*sol*inv[i]%MOD;
    return sol;
}

int main()
{
  cin >> d >> k >> P;
  if(d % 2 == 0) {
    m++;
    while(d % 2 == 0)
      d /= 2, p[m]++;
  }
  for(int i = 3; 1LL * i * i <= d; i += 2) {
    if(d % i == 0) {
      m++;
      while(d % i == 0)
        d /= i, p[m]++;
    }
  }
  if(d > 1)
    p[++m]++;
  sol = 1;
  for(int i = 1; i <= 200; i++)
    inv[i] = lgput(i, MOD - 2);
  for(int i = 1; i <= m; i++)
    sol = 1LL * sol * comb(k + p[i] - 1, k - 1) % MOD;
  int lst = sol;
  for(int i = 1; i < k; i++) {
    for(int j = 1; j <= m; j++)
      lst = 1LL * lst * (k - i) * inv[k + p[j] - i] % MOD;
    sol += (i % 2 == 0 ? 1LL : -1LL) * comb(k, i) * lst % MOD;
    if(sol < 0)
      sol += MOD;
    if(sol > MOD)
      sol -= MOD;
  }
  ciur[1] = 1;
  for(int i = 2; i <= 1000; i++) {
    if(!ciur[i]) {
      for(int j = i * i; j <= 1000000; j += i)
        ciur[j] = 1;
    }
  }
  for(int i = 1; i <= P; i++)
    nrPrime += 1 - ciur[i];
  cout << 1LL * sol * comb(nrPrime, k) % MOD;
  return 0;
}