Напишите программу для определения количества целых чисел, лежащих на отрезке [X; Y] и представляющих собой сумму ровно K различных степеней целого числа B с целыми показателями.
Пример. Пусть X = 15, Y = 20, K = 2, B = 2. В данном примере три целых числа представляют собой сумму ровно двух целых степеней числа 2:
17 = 24 + 20,
18 = 24 + 21,
20 = 24 + 22.
Исходные данные
Первая строка содержит целые числа X и Y (1 ≤ X ≤ Y ≤ 231 − 1). Следующие две строки содержат целые числа K и B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
Результат
Выведите количество целых чисел, лежащих между X и Y, которые представляют собой сумму ровно K различных степеней целого числа B с целыми показателями.
Пример
исходные данные | результат |
---|
15 20
2
2
| 3
|
Источник задачи: Rybinsk State Avia Academy