Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different 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:

The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 2³¹−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

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.