CF1808E3 Minibuses on Venus (hard version)

这是该问题的困难版本。三种版本的区别仅在于 $n$ 和 $k$ 的约束条件。只有在解决了所有版本的问题后，你才能进行 hack。 Maxim 是金星上的一名小巴司机。 要乘坐 Maxim 的小巴，你需要一张车票。每张车票上都有一个由 $n$ 位数字组成的号码。然而，众所周知，金星居民使用的是 $k$ 进制数，而不是十进制。因此，车票号码可以看作是一个长度为 $n$ 的整数序列，每个数字都在 $0$ 到 $k-1$ 之间（包含 $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 2000$，$10^8 \le m \le 10^9 + 7$，$m$ 是质数），分别表示车票的位数、金星的进制和答案取模的质数。

输出一个整数，表示幸运车票的数量对 $m$ 取模后的结果。

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