//
// URAL 1057.cpp
// playground
//
// Created by Adam Chang on 2015/08/03.
// Copyright © 2015年 Adam Chang. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>
using namespace std;
unsigned int x = 0, y = 0, k = 0, b = 0;
unsigned int dp[33][33];//dp[depth][request numbers of 1]
void get_dp(){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= 32; i++) {
dp[i][0] = 1;
for (int j = 1; j <= 32; j++) {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
}
unsigned int get_ans(unsigned int a){
unsigned int ret = 0;
int hav = 0;
for (int i = 31; i >= 0; i--) {
if (a & (1 << i)) {
if (k >= hav) {
ret += dp[i][k-hav];
}
hav++;
}
}
return ret;
}
bitset<32> b_to_bin(unsigned int n){
vector<int> vec;
while (n) {
vec.push_back(n % b);
n /= b;
}
bitset<32> bit;
for (int i = 1; i <= vec.size(); i++) {
if (vec[(int)vec.size() - i] == 1) {
bit[(int)vec.size() - i] = 1;
}else if(vec[(int)vec.size() - i] == 0){
bit[(int)vec.size() - i] = 0;
}else {
for (int j = (int)vec.size() - i; j >= 0; j--) {
bit[j] = 1;
}
break;
}
}
return bit;
}
int main(){
cin >> x >> y >> k >> b;
get_dp();
bitset<32> bitx(b_to_bin(x));
bitset<32> bity(b_to_bin(y));
cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl;
return 0;
}