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:

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

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

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

### Input

The first line of input contains integers *X* and *Y*, separated with a space (1 ≤ *X* ≤ *Y* ≤ 2^{31}−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