#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r,f[][],ans;

int n,a[],K;

ll dfs1(int pos,int s,bool lim)

{

    if(pos==)return s;

    if(!lim&&f[pos][s]!=-)return f[pos][s];

    int end=K-; ll ret=;

    if(lim)end=a[pos];

    for(int i=;i<=end;i++)

        ret+=dfs1(pos-,s+i*(pos-),lim&&(i==end));

    if(!lim)f[pos][s]=ret;//!lim!

    return ret;

}

ll dfs(int pos,int s,int m,bool lim)

{

    if(s<)return ;//!

    if(pos==)return s;

    if(!lim&&f[pos][s]!=-)return f[pos][s];

    int end=K-; ll ret=;

    if(lim)end=a[pos];

    for(int i=;i<=end;i++)

    {

        if(pos>=m)ret+=dfs(pos-,s+i,m,lim&&(i==end));

        else ret+=dfs(pos-,s-i,m,lim&&(i==end));

    }

    if(!lim)f[pos][s]=ret;

    return ret;

}

ll calc(ll x)

{

    int n=;

    while(x)a[++n]=x%K,x/=K;

    memset(f,-,sizeof f);

    ll ret=dfs1(n,,);

    for(int i=;i<=n;i++)

    {

        memset(f,-,sizeof f);

        ret-=dfs(n,,i,);

    }

    return ret;

}

int main()

{

    scanf("%lld%lld%d",&l,&r,&K);

    printf("%lld\n",calc(r)-calc(l-));

    return ;

}