310278: CF1808E3. Minibuses on Venus (hard version)
Description
This is the hard version of the problem. The only difference between the three versions is the constraints on $n$ and $k$. You can make hacks only if all versions of the problem are solved.
Maxim is a minibus driver on Venus.
To ride on Maxim's minibus, you need a ticket. Each ticket has a number consisting of $n$ digits. However, as we know, the residents of Venus use a numeral system with base $k$, rather than the decimal system. Therefore, the ticket number can be considered as a sequence of $n$ integers from $0$ to $k-1$, inclusive.
The residents of Venus consider a ticket to be lucky if there is a digit on it that is equal to the sum of the remaining digits, modulo $k$. For example, if $k=10$, then the ticket $7135$ is lucky because $7 + 1 + 5 \equiv 3 \pmod{10}$. On the other hand, the ticket $7136$ is not lucky because no digit is equal to the sum of the others modulo $10$.
Once, while on a trip, Maxim wondered: how many lucky tickets exist? At the same time, Maxim understands that this number can be very large, so he is interested only in the answer modulo some prime number $m$.
The only line of the input contains three integers $n$, $k$ and $m$ ($1 \le n \le 10^{18}$, $1 \le k \le 2000$, $10^8 \le m \le 10^9 + 7$, $m$ is a prime number) — the number of digits on the ticket, the base of the numeral system on Venus, and the module for answer calculation.
OutputPrint one integer — the number of lucky tickets modulo $m$, i. e. the remainder after dividing the answer by $m$.
ExamplesInput3 2 1000000007Output
4Input
3 4 1000000007Output
28Note
In the first example, there are only four lucky tickets: $000$, $011$, $101$, and $110$.
Input
题意翻译
## 题目描述 马克西姆是一个金星上的迷你巴士司机。 为了乘坐他的车，你要买一张票。票上总是会有一些编号，总共有 $n$ 位数字。然而，金星上的居民们都使用 $k$ 进制的数字系统，而不是我们所用的十进制数字系统。据此，票的编码可以视为 $n$ 个整数包含于 $[0,k)$。 如果在这 $n$ 个数字中，存在一个数字等于其他 $n-1$ 个数的总和 $mod$ $k$。那么，他们就成这串数字为幸运数。举个例子，当 $k=10$ ，这个票的编码是 $7135$ 时，这串数就是幸运的。因为 $7+1+5\equiv 3(mod $ $10)$。同样地，$7136$ 就不满足此条件，因此，他不是幸运的数字。 在每一次的旅行中，马克西姆想知道：在长度为 $n$ 的所有数组成的数列里，能有多少张幸运的票？同时呢，马克西姆也知道这个数字非常大，所以，他只对关心答案对质数 $m$ 取模的结果。 ## 数据范围 对于 $100\%$ 的数据，满足：$1\leq n\leq 10^{18}$，$1\leq k\leq 2000$，$10^{8}\leq m\leq 10^9$Output
这个问题是“金星上的小巴（困难版本）”。在这个版本中，唯一的区别是对n和k的限制。只有当问题的所有版本都被解决时，你才能进行黑客攻击。
马克西姆是金星上的小巴司机。为了乘坐马克西姆的小巴，你需要一张车票。每张车票都有一个由n位数字组成的号码。然而，我们知道，金星上的居民使用的是以k为基数的数字系统，而不是十进制系统。因此，车票号码可以看作是一个由0到k-1（包括k-1）的n个整数的序列。
如果车票上有一个数字等于其余数字之和模k，那么金星上的居民认为这张车票是"幸运的"。例如，如果k=10，那么车票7135是幸运的，因为7+1+5≡3(mod10)。另一方面，车票7136不是幸运的，因为没有数字等于其他数字之和模10。
有一次，马克西姆在旅行中想知道：有多少幸运的车票存在？同时，马克西姆明白这个数字可能非常大，所以他只对模某个素数m的答案感兴趣。
输入输出数据格式：
输入数据：
输入只有一行，包含三个整数n、k和m（1≤n≤10^18，1≤k≤2000，10^8≤m≤10^9+7，m是素数）——车票上的数字数量、金星上数字系统的基数以及答案计算的模数。
输出数据：
打印一个整数——幸运车票的数量模m，即答案除以m后的余数。
示例：
输入：3 2 1000000007
输出：4
输入：3 4 1000000007
输出：28
注意：在第一个示例中，只有四张幸运的车票：000、011、101和110。题目大意： 这个问题是“金星上的小巴（困难版本）”。在这个版本中，唯一的区别是对n和k的限制。只有当问题的所有版本都被解决时，你才能进行黑客攻击。 马克西姆是金星上的小巴司机。为了乘坐马克西姆的小巴，你需要一张车票。每张车票都有一个由n位数字组成的号码。然而，我们知道，金星上的居民使用的是以k为基数的数字系统，而不是十进制系统。因此，车票号码可以看作是一个由0到k-1（包括k-1）的n个整数的序列。 如果车票上有一个数字等于其余数字之和模k，那么金星上的居民认为这张车票是"幸运的"。例如，如果k=10，那么车票7135是幸运的，因为7+1+5≡3(mod10)。另一方面，车票7136不是幸运的，因为没有数字等于其他数字之和模10。 有一次，马克西姆在旅行中想知道：有多少幸运的车票存在？同时，马克西姆明白这个数字可能非常大，所以他只对模某个素数m的答案感兴趣。 输入输出数据格式： 输入数据： 输入只有一行，包含三个整数n、k和m（1≤n≤10^18，1≤k≤2000，10^8≤m≤10^9+7，m是素数）——车票上的数字数量、金星上数字系统的基数以及答案计算的模数。 输出数据： 打印一个整数——幸运车票的数量模m，即答案除以m后的余数。 示例： 输入：3 2 1000000007 输出：4 输入：3 4 1000000007 输出：28 注意：在第一个示例中，只有四张幸运的车票：000、011、101和110。