题目描述

原题来自：NEERC 2000 Central Subregional，题面详见 [Ural 1057]。

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

$$\red{\begin{align} 17&=2^4+2^0 \\ 18&=2^4+2^1 \\ 20&=2^4+2^2 \end{align}​​​​} $$

输入格式

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

输出格式

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

样例

输入样例

15 20
2
2

输出样例

3

提示

对于全部数据，$\red{1\le X\le Y\le 2^{31}-1,1\le K\le 20,2\le B\le 10}$。