Codeforces Round 861 (Div. 2) |
---|
Закончено |
Это простая версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и $$$k$$$. Вы можете делать взломы, только если все три версии задачи сданы.
Максим — водитель маршрутки на планете Венера.
Чтобы проехаться на маршрутке Максима, необходимо иметь билет. У каждого билета есть номер, состоящий из $$$n$$$ цифр. Но, как известно, жители Венеры пользуются не десятичной системой счисления, а системой счисления по основанию $$$k$$$. Поэтому можно считать, что номер билета — это последовательность из $$$n$$$ целых чисел от $$$0$$$ до $$$k-1$$$ включительно.
Жители Венеры считают билет счастливым, если на нем найдется цифра, равная сумме остальных цифр по модулю $$$k$$$. Например, если $$$k=10$$$, то билет $$$7135$$$ является счастливым, поскольку $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$. С другой стороны, билет $$$7136$$$ счастливым не является, поскольку ни одна цифра не равна сумме всех остальных по модулю $$$10$$$.
Однажды Максим, выполняя очередную поездку, задумался: а сколько всего существует счастливых билетов? При этом Максим понимает, что это число может быть очень велико, поэтому его интересует лишь остаток от деления ответа на некоторое простое число $$$m$$$.
В единственной строке входных данных находится три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 30$$$, $$$10^8 \le m \le 10^9 + 7$$$, $$$m$$$ — простое) — количество цифр на билете, основание системы счисления на Венере, и модуль, по которому надо найти ответ.
Выведите одно целое число — количество счастливых билетов по модулю $$$m$$$, т. е. остаток от деления ответа на $$$m$$$.
3 2 1000000007
4
3 4 1000000007
28
В первом примере существует всего четыре счастливых билета: $$$000$$$, $$$011$$$, $$$101$$$ и $$$110$$$.
Название |
---|