310276: CF1808E1. Minibuses on Venus (easy version)
Description
This is the easy 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 100$, $1 \le k \le 30$, $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 100$，$1\leq k\leq 30$，$10^{8}\leq m\leq 10^9$Output
这是一个关于金星上的小巴车票的问题。车票由n位数字组成，数字基于k进制（k为小于等于30的整数）。如果一个车票的某一位数字等于其他所有位数字之和模k的结果，则这个车票被认为是“幸运的”。需要计算有多少张这样的幸运车票，结果对一个大质数m取模。
输入数据格式：
输入包含三个整数n、k和m（1≤n≤100，1≤k≤30，$10^8$≤m≤$10^9+7$，m是质数）——车票的位数、金星数字系统的基数以及答案计算时的模数。
输出数据格式：
输出一个整数——幸运车票的数量模m的结果。
例如：
输入：3 2 1000000007
输出：4
输入：3 4 1000000007
输出：28
注意：
在第一个例子中，只有四张幸运车票：000、011、101和110。题目大意： 这是一个关于金星上的小巴车票的问题。车票由n位数字组成，数字基于k进制（k为小于等于30的整数）。如果一个车票的某一位数字等于其他所有位数字之和模k的结果，则这个车票被认为是“幸运的”。需要计算有多少张这样的幸运车票，结果对一个大质数m取模。 输入数据格式： 输入包含三个整数n、k和m（1≤n≤100，1≤k≤30，$10^8$≤m≤$10^9+7$，m是质数）——车票的位数、金星数字系统的基数以及答案计算时的模数。 输出数据格式： 输出一个整数——幸运车票的数量模m的结果。 例如： 输入：3 2 1000000007 输出：4 输入：3 4 1000000007 输出：28 注意： 在第一个例子中，只有四张幸运车票：000、011、101和110。