#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=45;
int l,r,k,b;
int c[N][N];
int dp(int sum)
{
    vector<int> nums;
    while(sum)nums.push_back(sum%b),sum/=b;
    int res=0;
    int ls=0;
    for(int i=nums.size()-1;~i;i--)
    {

        int x=nums[i];
        if(x>1)
        {
            res+=c[i+1][k-ls];
            break;
        }
        if(x)res+=c[i][k-ls],ls++;
        if(ls>k)break;//非法情况不能统计
        if(ls==k&&!i)res++;
    }
    return res;
}
void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j)c[i][j]=1;
            else c[i][j]=c[i-1][j-1]+c[i-1][j];
}
signed main()
{
    cin>>l>>r>>k>>b;
    init();
    cout<<dp(r)-dp(l-1)<<endl;
    return 0;
}