Minibuses on Venus (hard version)
Contest: Codeforces Round 861 (Div. 2)
Difficulty rating: 2800
Tags: brute force, combinatorics, dp, math

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$$$.

Input format:
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.

Output format:
Print one integer — the number of lucky tickets modulo $$$m$$$, i. e. the remainder after dividing the answer by $$$m$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are only four lucky tickets: $$$000$$$, $$$011$$$, $$$101$$$, and $$$110$$$.

Example input:
3 2 1000000007

Example output:
4

Example input:
3 4 1000000007

Example output:
28

Editorial:
First read the editorial for problems E1 and E2. This section is a continuation and improvement of ideas from previous sections.
Let's calculate how many such digits $$$x$$$ can exist in total for a fixed $$$S$$$ modulo $$$k$$$ that: $$$$$$2 \cdot x \equiv S \pmod{k}$$$$$$. To do this we need to consider two cases:
• $$$k$$$ is odd. Then there can exist exactly one such digit $$$x$$$ from $$$0$$$ to $$$k - 1$$$, provided that $$$S$$$ – is odd (and it will equal exactly $$$\frac{S + k}{2}$$$).
• $$$k$$$ is even. Then there can be two such digits $$$x_1, x_2$$$ from $$$0$$$ to $$$k - 1$$$, provided that $$$S$$$ – is even (with $$$x_1 = \frac{k}{2}, x_2 = \frac{S + k}{2}$$$).
Let's solve the problem when $$$k$$$ is odd. Calculate how many different $$$S$$$ exist that for them there exists a digit $$$x$$$ (denote the set of such $$$S$$$ as $$$cnt_1$$$), and calculate how many different $$$S$$$ exist that for them there is no such digit $$$x$$$ (denote the set of such $$$S$$$ as $$$cnt_0$$$).
If $$$S$$$ enters $$$cnt_0$$$, then the number of unsurprising ticket numbers will be $$$k^{n-1}$$$ (Since the total numbers $$$k^n$$$ are exactly $$$\frac{1}{k}$$$ of them will have some $$$S$$$ from $$$0$$$ to $$$k - 1$$$ modulo $$$k$$$). So it is sufficient to add $$$|cnt_0| \cdot k^{n-1}$$$ to the number of unsurprising tickets.
If $$$S$$$ enters $$$cnt_1$$$, let's use the following trick: subtract from each digit in the number $$$x$$$. Now we have reduced the original problem to the case where $$$x = 0$$$.
Now let's count the DP $$$f[i][flag]$$$ – the number of unlucky numbers, where:
• $$$i$$$ – how many digits of the ticket we've already looked at
• $$$flag = 1$$$ if the current sum of digits is greater than zero, and $$$flag = 0$$$ otherwise.
This DP can be counted in $$$O(\log n)$$$, again using the binary exponentiation of the matrix $$$2 \times 2$$$ (the content of the matrix is justified by the fact that the numbers must not contain $$$x = 0$$$): $$$\begin{pmatrix} 0 & k - 1\\ 1 & k - 2 \end{pmatrix}$$$
After calculating the DP, it is necessary to enumerate all possible variants of $$$x$$$ and variants of $$$S'$$$. If the condition is satisfied: $$$$$$2 \cdot x \equiv (S' + x \cdot n) \pmod{k}$$$$$$.
Then we can add to the number of unsurprising numbers:
• $$$f[n][0]$$$ if $$$S' = 0$$$
• $$$\frac{f[n][1]}{k - 1}$$$ if $$$S' \neq 0$$$ (note that division must be done modulo $$$m$$$). The reason for division is that $$$f[n][1]$$$ is the number of all numbers with $$$S' \neq 0$$$, and we need the number of numbers with some particular sum of $$$S'$$$.
The approach to solving for even $$$k$$$ will be almost identical to the approach for odd $$$k$$$. The difference will be that we can now have either two $$$x_1, x_2$$$ when $$$S$$$ is fixed, or none. When there are no $$$x$$$-ones, the solution is the same as the solution for $$$cnt_0$$$ of odd $$$k$$$. When there is $$$x_1, x_2$$$, we can see that they differ by $$$\frac{k}{2}$$$. So let's again subtract $$$x_1$$$ from each digit in the number and then double each digit after that. That is, we now work with the numbers $$$0, 2, \ldots, 2\cdot (k - 2), 0, 2, \ldots (k - 2)$$$. The matrix for DP transitions will now have the form: $$$\begin{pmatrix} 0 & k - 2\\ 2 & k - 4 \end{pmatrix}$$$
After calculating the DP, it is necessary to enumerate all matching pairs $$$x_1, x_2$$$ and variants of $$$S'$$$. If the condition is satisfied: $$$$$$2 \cdot x_1 \equiv (S' + x_1 \cdot n) \pmod{k}$$$$$$
Then we can add to the number of unsurprising numbers:
• $$$\frac{f[n][0]}{2}$$$ if $$$S' = 0$$$ (note that division must be done modulo $$$m$$$). The division is justified by the fact that $$$f[n][0]$$$ is the number of all numbers with $$$S' = 0$$$, but now we have two different "zero" sums (since we have dominated all numbers by 2).
• $$$\frac{f[n][1]}{k - 2}$$$ if $$$S' \neq 0$$$ (note that division must be done modulo $$$m$$$). The reason for division is that $$$f[n][1]$$$ is the number of all numbers with $$$S' \neq 0$$$, and we need the number of numbers with some particular sum of $$$S'$$$.