Minibuses on Venus (easy version)
Contest: Codeforces Round 861 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, divide and conquer, dp

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

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

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, let's rephrase the problem condition a bit. A ticket number is lucky if ($$$a_i$$$ – the digit that stands at position $$$i$$$ in the number) is satisfied: $$$$$$ a_i \equiv (a_1 + a_2 + \ldots + a_{i-1} + a_{i+1} + \ldots + a_{n-1} + a_n) \pmod{k} $$$$$$
Let $$$S$$$ be the sum of all digits of the number. Then we can rewrite the surprise condition: $$$$$$ a_i \equiv S - a_i \pmod{k} $$$$$$ $$$$$$ 2 \cdot a_i \equiv S \pmod{k} $$$$$$
Thus, if among the digits of the ticket there is such a digit $$$x$$$ that: $$$$$$2 \cdot x \equiv S \pmod{k}$$$$$$
Then the ticket is lucky.
Also note that there are $$$k^n$$$ numbers of tickets in total. Let's count how many nosurprising tickets exist. Then, by subtracting this number from $$$k^n$$$, we will get the answer to the original problem. So now our goal is to count the number of non-surprising tickets.
Given a fixed sum $$$S$$$, there are numbers $$$x$$$ that: $$$$$$2 \cdot x \equiv S \pmod{k}$$$$$$
Therefore, in order for a number with sum $$$S$$$ to be unlucky, it must not contain these digits.
Let us fix what $$$S$$$ modulo $$$k$$$ will equal.
Now, let's make a DP $$$f[i][sum]$$$, where:
• $$$i$$$ – index of the digit to be processed in the ticket
• $$$sum$$$ – the current sum of digits of the ticket, modulo $$$k$$$
The basis of DP – $$$f[0][0] = 1$$$. We will build transitions from the state $$$f[i][sum]$$$ by going through the digit $$$y$$$, which we will put at position $$$i$$$. Keep in mind that we cannot use such $$$y$$$ that: $$$$$$2 \cdot y \equiv S \pmod{k}$$$$$$
Depending on $$$y$$$ we recalculate $$$sum$$$. The number of unlucky ticket numbers, with sum $$$S$$$ modulo $$$k$$$ will be stored in $$$f[n][S]$$$.