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 the integer B.

Example. Let X = 15, Y = 20, K = 2, B = 2. By this example three integers are the sum of exactly two integer degrees of number 2:

The first line contains integers X and Y (1 ≤ X ≤ Y ≤ 2³¹ − 1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

Output the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.