Particles

Time limit5sMemory limit64 MB

Summary

Count functions from N chambers to themselves such that applying the function K times returns every element to its start, modulo M.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Number theory
Solved: No attempts yet

Problem

Mirko was hired as a physicist at the European Organization for Nuclear Research (CERN), and his first assignment is to draw the blueprint of the newest particle accelerator.

The accelerator has exactly $N$ chambers, and at the moment an experiment starts every chamber holds one particle. Each chamber has exactly one chamber that follows it. Every second, all particles move at the same time from the chamber they are in to the chamber that follows it. If chamber $B$ follows chamber $A$ , chamber $A$ does not have to follow chamber $B$ , although two chambers may follow each other.

The condition that matters most for the experiment is that after $K$ seconds every particle is back in the chamber it started in. Mirko wants to know how many blueprints satisfy this condition. Two blueprints are different when some chamber is followed by a different chamber in each of them. The number of blueprints can be very large, so report only its remainder after division by $M$ .

Note that a chamber may follow itself.

Input

The first line contains two numbers $N$ and $K$ separated by a space ( $1 \le K \le N \le 30000$ ). $N$ is the total number of chambers Mirko has for building the accelerator, and $K$ is the time in seconds after which every particle must be back in its starting chamber.

The second line contains the modulus $M$ ( $1 \le M \le 10^9$ ).

Output

Print on the first line the number of different blueprints that satisfy the condition, modulo $M$ .

Examples3

Example 1
Input
```
2 1
1000
```
Expected output
```
1
```
Example 2
Input
```
3 2
1000
```
Expected output
```
4
```
Example 3
Input
```
4 4
6
```
Expected output
```
4
```