#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

constexpr int N = 500'000 + 5;

vector<int> f[N];

constexpr int64_t INF = 1LL << 60;

int64_t mul(int64_t a, int64_t b) {
  // a * b >= INF
  // a >= INF / b
  if (a >= INF / b)
    return INF;
  return min(a * b, INF);
}

constexpr int64_t qpow(int64_t a, int64_t k) {
  int64_t r = 1;
  while (k) {
    if (k & 1)
      r = mul(r, a);
    k >>= 1;
    a = mul(a, a);
  }
  return r;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  int64_t m;
  int k;
  while (cin >> n >> m >> k) {
    for (int i = 1; i <= m; ++i) {
      for (int j = i; j <= m; j += i) {
        f[j].push_back(i);
      }
    }

    if (n == 1) {
      if (k == 1) {
        cout << (2 * m + 1) * (2 * m + 1) - 2 * m - 1 << '\n';
      } else {
        cout << "0\n";
      }
    } else if (n == 2) {
      int ans = 0;
      // b = 0
      for (int a = -m; a <= m; ++a)
        ans += (1 + (a != 0)) == k; // {a, 0}
      // b != 0
      for (int b = 1; b <= m; ++b) {
        for (int p : f[b]) {
          const int q = b / p;
          if (p > q)
            break;
          if (const int a = p + q; a <= m) {
            // (x - p)(x - q) = 0
            ans += (1 + (p != q)) == k; // {a, b}
            // (x + p)(x + q) = 0
            ans += (1 + (p != q)) == k; // {-a, b}
          }
          if (const int a = q - p; a <= m) {
            // (x - p)(x + q) = 0
            ans += 2 == k; // {a, -b}
            if (p != q) {
              // (x + p)(x - q) = 0
              ans += 2 == k; // {-a, -b}
            }
          }
        }
      }
      cout << ans << '\n';
    } else {
      map<pair<int, int>, int> cnt;
      // b = 0
      // x = 0
      for (int a = -m; a <= m; ++a)
        cnt[{a, 0}]++;
      // x != 0
      for (int x = 1; x <= 710; ++x) {
        int64_t a = qpow(x, n - 1);
        if (abs(a) > m)
          break;
        cnt[{-a, 0}]++;
        if (n % 2 == 0)
          a = -a;
        cnt[{-a, 0}]++;
      }
      int ans = 0;
      for (auto [ab, c] : cnt) {
        auto [a, b] = ab;
        //if (c == k) {
        //  cout << "x^" << n << " + " << a << "x + " << b << " = 0\n";
        //}
        ans += c == k;
      }

      //cout << "ans = " << ans << '\n';

      // b != 0
      for (int b = 1; b <= m; ++b) {
        vector<int> as, asn;
        for (int x : f[b]) {
          // b > 0
          {
            int64_t xn1 = qpow(x, n - 1);
            // x > 0
            {
              int xn1a = -b / x;
              int64_t a = xn1a - xn1;
              //cout << "x = " << x << ", ";
              //cout << "xn1a = " << xn1a << ", xn1 = " << xn1 << ", a = " << a << '\n';
              if (abs(a) <= m)
                as.push_back(a);
            }
            // x < 0
            {
              int xn1a = b / x;
              int64_t a = xn1a;
              if (n & 1) a -= xn1;
              else a += xn1;
              //cout << "x = " << -x << ", ";
              //cout << "xn1a = " << xn1a << ", xn1 = " << xn1 << ", a = " << a << '\n';
              if (abs(a) <= m)
                as.push_back(a);
            }
          }
          // b < 0
          {
            int64_t xn1 = qpow(x, n - 1);
            // x > 0
            {
              int xn1a = b / x;
              int64_t a = xn1a - xn1;
              if (abs(a) <= m)
                asn.push_back(a);
            }
            // x < 0
            {
              int xn1a = b / -x;
              int64_t a = xn1a;
              if (n & 1) a -= xn1;
              else a += xn1;
              if (abs(a) <= m)
                asn.push_back(a);
            }

          }
        }
        ranges::sort(as);
        ranges::sort(asn);

        //cout << "b = " << b << "\n";
        //for (auto ai : as)
        //  cout << ai << " ";
        //cout << '\n';
        //cout << "b = " << -b << '\n';
        //for (auto ai : asn)
        //  cout << ai << " ";
        //cout << '\n';
        if (not as.empty()) {
          int v = as[0];
          int c = 1;          
          for (int i = 1; i < ssize(as); ++i) {
            if (v == as[i]) {
              c += 1;
            } else {
              ans += c == k;
              v = as[i];
              c = 1;
            }
          }
          ans += c == k;
        }
        if (not asn.empty()) {
          int v = asn[0];
          int c = 1;          
          for (int i = 1; i < ssize(asn); ++i) {
            if (v == asn[i]) {
              c += 1;
            } else {
              ans += c == k;
              v = asn[i];
              c = 1;
            }
          }
          ans += c == k;
        }
      }
      cout << ans << '\n';
    }
    for (int i = 1; i <= m; ++i)
      f[i].clear();
  }
  return 0;
}