310277: CF1808E2. Minibuses on Venus (medium version)
Description
This is the medium 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 100$, $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 100$，$10^{8}\leq m\leq 10^9$Output
这个问题是关于金星上的小巴车票的。在金星上，数字系统是基于k进制的，而不是十进制。一个车票被认为是非常“幸运”的，如果车票上的某个数字等于其他所有数字之和（对k取模）。例如，如果k=10，那么车票7135是幸运的，因为7 + 1 + 5 ≡ 3 (mod 10)。问题是，在给定n个数字和k进制的条件下，计算有多少张“幸运”的车票，结果对一个大质数m取模。
输入输出数据格式：
输入：
只有一行，包含三个整数n, k和m (1 ≤ n ≤ 10^18, 1 ≤ k ≤ 100, 10^8 ≤ m ≤ 10^9 + 7，m是一个质数) —— 车票上的数字数量，金星上的数字系统的基础，以及答案计算的模数。
输出：
打印一个整数 —— 幸运车票的数量模m，即答案除以m后的余数。
示例：
输入：3 2 1000000007
输出：4
输入：3 4 1000000007
输出：28
注意：在第一个例子中，只有四张幸运车票：000, 011, 101, 和 110。题目大意： 这个问题是关于金星上的小巴车票的。在金星上，数字系统是基于k进制的，而不是十进制。一个车票被认为是非常“幸运”的，如果车票上的某个数字等于其他所有数字之和（对k取模）。例如，如果k=10，那么车票7135是幸运的，因为7 + 1 + 5 ≡ 3 (mod 10)。问题是，在给定n个数字和k进制的条件下，计算有多少张“幸运”的车票，结果对一个大质数m取模。 输入输出数据格式： 输入： 只有一行，包含三个整数n, k和m (1 ≤ n ≤ 10^18, 1 ≤ k ≤ 100, 10^8 ≤ m ≤ 10^9 + 7，m是一个质数) —— 车票上的数字数量，金星上的数字系统的基础，以及答案计算的模数。 输出： 打印一个整数 —— 幸运车票的数量模m，即答案除以m后的余数。 示例： 输入：3 2 1000000007 输出：4 输入：3 4 1000000007 输出：28 注意：在第一个例子中，只有四张幸运车票：000, 011, 101, 和 110。