Задача I. Интригующие нули

Автор:Евгений Татаринов, Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:128 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Новогодние каникулы — отличное время для отдыха и, как оказалось, для изучения математики. Дед Мороз решил разобраться в комбинаторике и столкнулся с формулой Cnk. Он представил, что у него есть n подарков и мешок, вмещающий ровно k вещей, и количество вариантов заполнения мешка выражается этой формулой.

Дед Мороз поделился своим открытием с детьми, и те в ответ рассказали ему о системах счисления. Заинтригованный Дед Мороз решил вычислить количество способов заполнить мешок и представить число в d-ичной системе счисления, где d — количество детей на празднике.

Однако, когда Дед Мороз заканчивал запись числа на снегу, он обнаружил много нулей в конце и запутался. Помогите ему разобраться! Скажите, сколько нулей должно быть в конце записи числа, чтобы все было правильно.

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

Единственная строка содержит числа n, k и d - количество подарков, вместимость мешка и количество детей на празднике.

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

Выведите количество нулей в конце записи числа Cnk в d-ичной системе счисления.

Ограничения

2 ≤ n, k, d ≤ 109.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
n, kd
1102 ≤ k ≤ n ≤ 102 ≤ d ≤ 36
2202 ≤ k ≤ n ≤ 1032 ≤ d ≤ 36
3202 ≤ k ≤ n ≤ 1052 ≤ d ≤ 105
3502 ≤ k ≤ n ≤ 1092 ≤ d ≤ 109

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

Стандартный вход Стандартный выход
1
12 3 2 
2

0.075s 0.011s 15