Это средняя версия задачи. Различия между версиями заключаются в ограничениях на \(n\) и \(k\). Вы можете делать взломы, только если все три версии задачи сданы.
Максим — водитель маршрутки на планете Венера.
Чтобы проехаться на маршрутке Максима, необходимо иметь билет. У каждого билета есть номер, состоящий из \(n\) цифр. Но, как известно, жители Венеры пользуются не десятичной системой счисления, а системой счисления по основанию \(k\). Поэтому можно считать, что номер билета — это последовательность из \(n\) целых чисел от \(0\) до \(k-1\) включительно.
Жители Венеры считают билет счастливым, если на нем найдется цифра, равная сумме остальных цифр по модулю \(k\). Например, если \(k=10\), то билет \(7135\) является счастливым, поскольку \(7 + 1 + 5 \equiv 3 \pmod{10}\). С другой стороны, билет \(7136\) счастливым не является, поскольку ни одна цифра не равна сумме всех остальных по модулю \(10\).
Однажды Максим, выполняя очередную поездку, задумался: а сколько всего существует счастливых билетов? При этом Максим понимает, что это число может быть очень велико, поэтому его интересует лишь остаток от деления ответа на некоторое простое число \(m\).
