### Statement

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.

### 代码

#include
using namespace std;
int k,b,f[50][50];
void init(){
f[0][0]=1;
for (int i=1;i<50;i++){
f[i][0]=f[i-1][0];
for (int j=1;j<=i;j++){
f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
}
int solve(int l){
vectorv;
while(l){
v.push_back(l%b);
l/=b;
}
int cnt=0,ans=0;
for (int i=v.size()-1;~i;i--){
if (v[i]==1){
ans+=f[i][k-cnt];
cnt++;
if (cnt==k) break;
}
if (v[i]>1){
ans+=f[i+1][k-cnt];
break;
}
}
if (cnt==k) ans++;
return ans;
}
int main(){
ios::sync_with_stdio(false);
init();int x,y;
cin>>x>>y>>k>>b;
cout<