这是问题的困难版本。三个版本之间的唯一区别是 $$$n$$$ 和 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Maxim 是金星上的一名小巴司机。
乘坐美心小巴需要车票。每张票都有一个由 $$$n$$$ 数字组成的号码。然而,正如我们所知,金星上的居民使用以 $$$k$$$ 为基数的数字系统,而不是十进制。因此,票号可以被视为从 $$$0$$$ 到 $$$k-1$$$(含)的 $$$n$$$ 整数序列。
金星的居民认为,如果票上有一个数字等于剩余数字的总和,模$$$k$$$,那么这张票就是幸运的。例如,如果 $$$k=10$$$,则票 $$$7135$$$ 是幸运的,因为 $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$。另一方面,$$$7136$$$ 这张票并不幸运,因为没有一个数字等于其他数字对 $$$10$$$ 取模后的总和。
有一次,在一次旅行中,马克西姆想知道:幸运券到底有多少张?同时,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$$$ 是 a质数)— 票上的位数、金星数字系统的基数以及答案计算模块。
输出
打印一个整数 - 幸运彩票的数量以 $$$m$$$ 为模,即 e.答案除以 $$$m$$$ 后的余数。
示例
输入 #1
3 2 1000000007
输出 #1
4
输入 #2
3 4 1000000007
输出 #2
28
注意
在第一个示例中,只有四张幸运票:$$$000$$$、$$$011$$$、$$$101$$$ 和 $$$110$$$。