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

const int N=35;
int K, B;
int f[N][N];

int main(){
    int l, r;
    cin>>l>>r>>K>>B;
    // 预处理组合数
    function<void()> func=[&](){
        for(int i=0; i<N; ++i)
            for(int j=0; j<=i; ++j){
                if(!j) f[i][j]=1;
                else f[i][j]=f[i-1][j]+f[i-1][j-1];
            }
    };
    func();

    // 数位DP
    function<int(int)> dp=[](int n){
        if(!n) return 0;
        vector<int> nums;
        while(n) nums.push_back(n%B), n/=B; //B进制表示
        int res=0;
        int pre=0;
        for(int i=nums.size()-1; i>=0; --i){ // 从高位向低位枚举
            int x=nums[i];
            if(x){ // 如果该位为0继续从高位枚举, 如果该位大于0, 考虑该位取1和取大于1的情况
                res+=f[i][K-pre];
                if(x>1){
                    if(K-pre-1>=0) res+=f[i][K-pre-1];
                    break;
                }
                else{
                    pre++;
                    if(pre>K) break;
                }
            }
            if(!i && pre==K) res++;
        }
        return res;
    };

    cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}