Số lượng bậc ( DEGREE )

Giới hạn
  • Thời gian: 0.065s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Một số nguyên dương A gọi là có bậc K đối với cơ số B nếu như :
• A = B^x1 + B^x2 + … + B^xk
( trong đó x1 , x2 , … , xk là các số nguyên không âm thoả mãn x1 <> x2 <> x3 … <> xk )
Ví dụ :
• 17 có bậc 2 đối với cơ số 2 vì 17 = 2^4 + 2^0 .
• 151 có bậc 3 đối với cơ số 5 vì 151 = 5^3 + 5^2 + 5^0.
Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.
Giới hạn :
• 1 <= X <= Y <= 10^9
• 1 <= K <= 25, 2 <= B <= 9
• Chạy được với bộ nhớ thông báo < 800 K bạn mới thực sự là thành công

Input

1 dòng gồm 4 số nguyên dương X , Y , K , B

Output

Gồm 1 dòng duy nhất ghi ra số lượng số tìm được .

Example

Input:
15 20 2 2

Output:
3 
( Giải thích : Đó là các số 17 = 2^4 + 2^0 , 18 = 2^4 + 2^1 , 20 = 2^4 + 2^2 )


  • Người up: hard7771988
  • Điểm: 0.32
  • Ngôn ngữ cho phép:
  • Nguồn bài: Rybinsk State Avia Academy