Это сложная версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и $$$k$$$. Вы можете делать взломы, только если все три версии задачи сданы.

Максим — водитель маршрутки на планете Венера.

Чтобы проехаться на маршрутке Максима, необходимо иметь билет. У каждого билета есть номер, состоящий из $$$n$$$ цифр. Но, как известно, жители Венеры пользуются не десятичной системой счисления, а системой счисления по основанию $$$k$$$. Поэтому можно считать, что номер билета — это последовательность из $$$n$$$ целых чисел от $$$0$$$ до $$$k-1$$$ включительно.

Жители Венеры считают билет счастливым, если на нем найдется цифра, равная сумме остальных цифр по модулю $$$k$$$. Например, если $$$k=10$$$, то билет $$$7135$$$ является счастливым, поскольку $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$. С другой стороны, билет $$$7136$$$ счастливым не является, поскольку ни одна цифра не равна сумме всех остальных по модулю $$$10$$$.

Однажды Максим, выполняя очередную поездку, задумался: а сколько всего существует счастливых билетов? При этом Максим понимает, что это число может быть очень велико, поэтому его интересует лишь остаток от деления ответа на некоторое простое число $$$m$$$.