Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly Kdifferent integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.
Input
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
Output
Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.
Sample
Problem Source: Rybinsk State Avia Academy