#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=35;
int l,r,k,b;
int a[N],a1;
int f[N][N][2];
int dp(int pos,int st,int op)
{
    if(pos==0) return st==k;
    if(f[pos][st][op]!=-1)
    {
        return f[pos][st][op];
    }
    int res=0;
    if(op)
    {
        int hh=min(a[pos],(int)1);
        for(int i=0;i<=hh;i++)
        {
            res+=dp(pos-1,st+i,op&&i==a[pos]);
        }
    }else{
        for(int i=0;i<=1;i++)
        {
            res+=dp(pos-1,st+i,0);
        }
    }

    return f[pos][st][op]=res;
}
int get(int x)
{
    a1=0;
    memset(f,-1,sizeof f);
    while(x) a[++a1]=x%b,x=x/b;
    return dp(a1,0,1);
}
signed main()
{
    cin>>l>>r>>k>>b;
    cout<<get(r)-get(l-1)<<endl;
    return 0;
}