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

Автор:Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1018

1 ≤ k ≤ 20

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

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

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

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

Стандартный вход Стандартный выход
1
30 3
10
2
7 2
7

0.071s 0.014s 13