Problem Description

This problem is translated from PA 2020 Round 4 Malowanie płotu.

This autumn’s weather has completely ruined the paint on Mr. Potyczek’s fence. The fence needs to be treated as soon as possible with a special blue waterproof coating, so that the coming winter will not cause irreversible damage. Mr. Potyczek asked his neighbor’s hardworking son, Bytie, to do the job. The boy finished the task this morning, but he did it quite carelessly because he was in a hurry to take part in the next round of PA.

Mr. Potyczek’s fence consists of $n$ wooden slats, and each slat is divided into $m$ equal-length segments. Bytie applied the waterproof coating only once on each slat, from top to bottom. Unfortunately, this may still not be enough to cover the whole fence. However, on each slat, the coated segments form one continuous block, and each segment is either fully coated or not coated at all. Moreover, the part of the fence coated by the boy is “consistent”, meaning that on every two consecutive slats, the coated blocks have a non-empty intersection interval.

For example, a painted fence may look like the figure below.

The situation shown below is impossible for the following three reasons.

• Slat $1$ is not coated at all.
• The middle segment of slat $3$ (which should be part of the consistent overlap) is not coated.
• For slats $5,6$, the intersection of the coated parts is empty.

Write a program to compute how many different ways Bytie can paint the fence following the rules above. If there is a segment of the fence that is painted in one way but not painted in another way, then the two ways are considered different. The number of ways can be very large, so you only need to output its remainder modulo the prime $p$.

Input Format

The input contains one line with three integers $n, m, p$, representing the number of slats, the number of segments on each slat, and the prime $p$, respectively.

Output Format

Output one integer: the number of valid painting ways modulo $p$.

3 2 100000007

17

6 9 813443923

57

Hint

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \times m \le 10^7$, $10^8 \le p \le 10^9$, and $p \in \mathbb{P}$.

Translated by ChatGPT 5