E2. Маршрутки на Венере (средняя версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это средняя версия задачи. Различия между версиями заключаются в ограничениях на $$$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 10^{18}$$$, $$$1 \le k \le 100$$$, $$$10^8 \le m \le 10^9 + 7$$$, $$$m$$$ — простое) — количество цифр на билете, основание системы счисления на Венере, и модуль, по которому надо найти ответ.

Выходные данные

Выведите одно целое число — количество счастливых билетов по модулю $$$m$$$, т. е. остаток от деления ответа на $$$m$$$.

Примеры
Входные данные
3 2 1000000007
Выходные данные
4
Входные данные
3 4 1000000007
Выходные данные
28
Примечание

В первом примере существует всего четыре счастливых билета: $$$000$$$, $$$011$$$, $$$101$$$ и $$$110$$$.