Masala #M080C

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.