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:

17 = 2^{4} + 2^{0},

18 = 2^{4} + 2^{1},

20 = 2^{4} + 2^{2}.

### Input

The first line contains integers *X* and *Y* (1 ≤ *X* ≤ *Y* ≤ 2^{31} − 1). The next two lines contain integers *K* and *B* (1 ≤ *K* ≤ 20; 2 ≤ *B* ≤ 10).

### Output

Output 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