import java.util.*;
public class Main{
    static int N = 35;
    static int k, b;
    static int f[][] = new int[N][N];

    static void init(){
        for(int i = 0; i < N; i ++){
            for(int j = 0; j <= i; j ++){
                if(j == 0) f[i][j] = 1;
                else f[i][j] = f[i-1][j] + f[i-1][j-1];
            }
        }
    }

    static int dp(int n){
        if(n == 0) return 0;
        List<Integer> arr = new ArrayList();
        while(n > 0){
            arr.add(n % b);
            n /= b;
        }
        int res = 0, last = 0;  //  只能选0或1，选其他数就不符合题意
        for(int i = arr.size()- 1; i >= 0; i --){
            int x = arr.get(i);
            if(x > 0){
                res += f[i][k - last];  //  只要不是0就可以选0，当前选0 前面last个1，
                if(x > 1){
                    res += f[i][k - last - 1];  //  可以选1，不能选 ai，所以后面就断子绝孙了
                    break;
                }else{
                    last++;
                    if(last == k){  //  后面只能选全0了，当前有一个后面全选0前面k个1的数 res++
                        res++;  
                        break;
                    } 
                }
            }//  x=0的话只能选本身0，直接走到下一个节点
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r = sc.nextInt();
        k = sc.nextInt();
        b = sc.nextInt();
        init();
        System.out.println(dp(r) - dp(l-1));
    }
}