| Автор: | Евгений Татаринов, Денис Лысенко | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 128 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Новогодние каникулы — отличное время для отдыха и, как оказалось, для изучения математики. Дед Мороз решил разобраться в комбинаторике и столкнулся с формулой Cnk. Он представил, что у него есть n подарков и мешок, вмещающий ровно k вещей, и количество вариантов заполнения мешка выражается этой формулой.
Дед Мороз поделился своим открытием с детьми, и те в ответ рассказали ему о системах счисления. Заинтригованный Дед Мороз решил вычислить количество способов заполнить мешок и представить число в d-ичной системе счисления, где d — количество детей на празднике.
Однако, когда Дед Мороз заканчивал запись числа на снегу, он обнаружил много нулей в конце и запутался. Помогите ему разобраться! Скажите, сколько нулей должно быть в конце записи числа, чтобы все было правильно.
Единственная строка содержит числа n, k и d - количество подарков, вместимость мешка и количество детей на празднике.
Выведите количество нулей в конце записи числа Cnk в d-ичной системе счисления.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | |
|---|---|---|---|
| n, k | d | ||
| 1 | 10 | 2 ≤ k ≤ n ≤ 10 | 2 ≤ d ≤ 36 |
| 2 | 20 | 2 ≤ k ≤ n ≤ 103 | 2 ≤ d ≤ 36 |
| 3 | 20 | 2 ≤ k ≤ n ≤ 105 | 2 ≤ d ≤ 105 |
| 3 | 50 | 2 ≤ k ≤ n ≤ 109 | 2 ≤ d ≤ 109 |
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|