Напишите программу для определения количества целых чисел, лежащих на отрезке [X; Y] и представляющих собой сумму ровно K различных степеней целого числа B с целыми показателями.

Пример. Пусть X = 15, Y = 20, K = 2, B = 2. В данном примере три целых числа представляют собой сумму ровно двух целых степеней числа 2:

Первая строка содержит целые числа X и Y (1 ≤ X ≤ Y ≤ 2³¹ − 1). Следующие две строки содержат целые числа K и B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

Выведите количество целых чисел, лежащих между X и Y, которые представляют собой сумму ровно K различных степеней целого числа B с целыми показателями.