猜灯谜啦

题目背景

猜灯谜啦！小神龙漫无目的的走在街上，突然它看到了一处猜灯谜的地方，走近一看，这次的灯谜好像是个数学问题......

题目描述

请你统计出 $[L,R]$ 区间内能够表示成 $K$ 个互不相等的 $B$ 的整数次幂之和的个数。

例如：$L=15,R=20,K=2,B=2$ 有且可以找出以下 $3$ 种情况：

• $17=2^4+2^0$
• $18=2^4+2^1$
• $20=2^4+2^2$

小神龙思考了好久都想不出来，只能麻烦天才的你啦！

输入格式

一行四个正整数，$L,R,K,B$。

输出格式

一行一个正整数，表示满足条件的数的个数。

样例 #1

样例输入 #1

15 20 2 2

样例输出 #1

3

提示

$1 \le L \le R \le 2^{31}-1$

$1 \le K \le 20$

$2 \le B \le 10$