E3. Minibuses on Venus (hard version)
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\).
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.
Print one integer — the number of lucky tickets modulo \(m\), i. e. the remainder after dividing the answer by \(m\).
In the first example, there are only four lucky tickets: \(000\), \(011\), \(101\), and \(110\).