Masala C

Find the number of integers lying on the interval [A,B] that can be represented as the sum of exactly Y distinct powers of an integer X, where both X and the powers are integers.

For example, for A=15, B=20, Y=2, and X=2, the answer is 3 because:

$17=2^4+2^0$

$18=2^4+2^1$

$20=2^4+2^2$

The first line contains two integers A and B $(1 <= A <= B <= 2^{31} - 1)$. The next two lines contain integers $Y$ and $X$ $(1 <= Y <= 20, 2 <= X <= 10)$

Print a single integer - the answer to the problem.