CF1808E2 Minibuses on Venus (medium version)

这是该问题的中等版本。三种版本的唯一区别在于 $n$ 和 $k$ 的约束条件。只有当你解决了所有版本的问题后，才能进行 Hack。 Maxim 是金星上的一名小巴司机。 要乘坐 Maxim 的小巴，你需要一张车票。每张车票上都有一个由 $n$ 位数字组成的号码。然而，众所周知，金星居民使用的是 $k$ 进制数字系统，而不是十进制。因此，车票号码可以看作是一个长度为 $n$ 的整数序列，每个整数的取值范围为 $0$ 到 $k-1$（包含两端）。 金星居民认为一张车票是幸运的，当且仅当存在某一位数字等于其余所有数字之和对 $k$ 取模的结果。举例来说，如果 $k=10$，那么车票 $7135$ 是幸运的，因为 $7+1+5 \equiv 3 \pmod{10}$。而车票 $7136$ 不是幸运的，因为没有任何一位数字等于其余数字之和模 $10$ 的结果。 有一次在旅途中，Maxim 想知道一共有多少张幸运车票。同时，Maxim 也明白这个数字可能非常大，因此他只关心答案对某个质数 $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$ 取模的结果。

在第一个样例中，只有四张幸运车票：$000$、$011$、$101$ 和 $110$。 由 ChatGPT 4.1 翻译