题目描述

求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于$K$个互不相等的$B$的整数次幂之和。$\\$ 例如，设$X=15,Y=20,K=2,B=2$，则有且仅有下列三个数满足题意：$\\$ $17=2^{4}+2^{0}$ $\\$ $18=2^{4}+2^{1}$ $\\$ $20=2^{4}+2^{2}$ $\\$

输入格式

第一行包含两个整数$X$和$Y$，接下来两行包含整数$K$ 和$B$。

输出格式

只包含一个整数，表示满足条件的数的个数。

输入输出样例 #1

输入 #1

15 20
2
2

输出 #1

3

说明/提示

数据范围与提示：$\\$ 对于全部数据，$1 \leq X \leq Y < 2^{31}, 1 \leq K \leq 20, 2 \leq B \leq 10$。