Description

Original source: NEERC 2000 Central Subregional, problem statement available at Ural 1057.

Find the number of integers in the given interval $[X, Y]$ that satisfy the following condition: the number is exactly equal to the sum of $K$ distinct integer powers of $B$. For example, given $X=15$, $Y=20$, $K=2$, $B=2$, there are exactly three numbers that meet the condition:

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

Input Format

The first line contains two integers $X$ and $Y$. The next two lines contain integers $K$ and $B$.

Output Format

Output a single integer representing the count of numbers that satisfy the condition.

Sample 1

15 20
2
2

3

Data Range and Hint

For all data, $1\le X\le Y\le 2^{31}-1$, $1\le K\le 20$, $2\le B\le 10$.