Задача I. Сборка по степеням ≡

Условие

На днях в Логландии прошла вселогландская олимпиада школьников по математике. Мальчик Влад не смог пройти на заключительный этап этой олимпиады, но его очень заинтересовала одна задача c финала. Суть данной задачи следующая: дан отрезок целых чисел от 1 до n, необходимо определить количество различных чисел, которое можно представить в виде суммы одной или более неповторяющихся степеней k (т. е. чисел k¹, k², k³ и т. д.)

Формат входных данных

В первой строке входных данных записано два целых числа n и k.

Формат выходных данных

Выведите одно число — количество различных чисел от 1 до n, которое можно представить в указанном виде.

Ограничения

1 ≤ n ≤ 10¹⁸

1 ≤ k ≤ 20

Пояснение к примерам

В первом примере мы может образовать из чисел 1, 3, 9, 27 следующие варианты: 1, 3, 4, 9, 10, 12, 13, 27, 28, 30.

Во втором примере мы можем представить все числа от 1 до 7.

Примеры тестов

30 3

10

7 2

7