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

const int N = 35;
int x, y, k, b;
// 组合数C_i^j
LL C[N][N];

void init() {
	for (int i = 0; i < N; i++) C[i][0] = C[i][i] = 1;
	for (int i = 2; i < N - 1; i++)
		for (int j = 1; j < i; j++)
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

int num[N];
LL solve(int x) {
	if (!x) return 0;
	int len = 0;
	// 注意，转换成B进制
	while (x) {
		num[++len] = x % b;
		x /= b;
	}

	int cnt = 0; // 已经用掉的1的个数
	LL ans = 0;
	for (int i = len; i >= 1; i--) {
		int now = num[i];
		if (now == 1) {
			// 当前位选0，且剩下的位数大于剩余的1的个数，
			// 那么答案可以增加这么多个：
			if (i > k - cnt) ans += C[i - 1][k - cnt];
			// 如果当前位选1，那么用掉的1个数++，并继续枚举低位
			cnt++;
			if (cnt > k) break;
		} else if (now > 1) {
			ans += C[i][k - cnt];
			break;
		} // else if (now ==0) 继续枚举低位;

		// 最后，检查边界值本身是否符合要求（正好有k个1）
		if (i == 1 && k == cnt) ans++;
	}
	return ans;
}

int main() {
	init();
	cin >> x >> y >> k >> b;
//	cout << solve(y) << ' ';
//	cout << solve(x - 1) << '\n';
	cout << (solve(y) - solve(x - 1)) << '\n';

	return 0;
}