#include<bits/stdc++.h>
using namespace std;
int n,m,k;
#define ll long long
const int N=5e5;const ll I=1e13;
vector<int>g[N+10];
ll mu(ll a,ll b){if(!a||!b)return 0;return (a<=I/b)?(a*b):I;}
ll qpow(ll a,ll b){
    ll c=1;
    for(;b;b>>=1){
        if(b&1){
            c=mu(a,c);
            if(c>=I)return I;
        }
        a=mu(a,a);
    }
    return c;
}
ll qp[N+10];
int main(){
    for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)
    g[j].push_back(i);
    while(~scanf("%d%d%d",&n,&m,&k)){
        if(n>=2){
            for(ll i=1;i<=m;i++)qp[i]=qpow(i,n);
            int ans=0;
            for(ll b_=1;b_<=m;b_++)for(ll X=-1;X<=1;X+=2){
                ll b=b_*X;
                vector<int>gg;
                for(ll x_:g[b_])for(ll Y=-1;Y<=1;Y+=2){
                    ll x=x_*Y,q=qp[x_];
                    if(Y==-1&&(n&1))q=-q;
                    if((q-b)%x==0){
                        ll a=(q-b)/x;
                        if(abs(a)<=m)gg.push_back(a);
                    }
                }
                sort(gg.begin(),gg.end());int sz=gg.size();
                for(int j=0,u=0;j<sz;j++){
                    u++;
                    if(j==sz-1||gg[j]!=gg[j+1]){
                        if(u==k)ans++;
                        u=0;
                    }
                }
            }
            int v=0;
            for(int i=1;i<=m;i++){
                ll z=qpow(i,n-1);
                if(z>m)break;
                v++;
            }
            if(n&1){
                if(k==1)ans+=m*2+1-v;
                else if(k==3)ans+=v;
            }
            else{
                if(k==1)ans+=m*2+1-v*2;
                else if(k==2)ans+=v*2;
            }
            printf("%d\n",ans);
        }
        else{
            if(k==1)printf("%lld\n",1ll*m*2*(m*2+1));
            else puts("0");
        }
    }
    return 0;
}