Fence Painting

This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 4 Malowanie płotu.

This autumn the weather has completely ruined the paint on Mr. Potyczek's fence. The fence, which is made of n wooden planks, each divided into m equal segments, must be quickly treated with a special blue waterproofing agent so that the coming winter does not cause irreparable damage. Mr. Potyczek has asked his neighbor's hardworking son, Bytie, to paint the fence.

Bytie painted exactly one continuous (i.e. contiguous) block of segments on each plank – note that on every plank, the painted segments are contiguous and a segment is either painted entirely or not at all. However, his work may not cover the entire fence. In addition, his painting is consistent: for every two consecutive planks the painted parts have a nonempty intersection (i.e. the two painted intervals share at least one common segment).

Formally, the fence consists of n planks. On each plank, Bytie chooses an interval [L_i, R_i] (with 1 ≤ L_i ≤ R_i ≤ m) to paint. For every adjacent pair of planks, i.e. for every i (1 ≤ i < n), the intervals must satisfy \[ \max(L_i, L_{i+1}) \le \min(R_i, R_{i+1}). \] Two ways of painting are considered different if there is at least one segment that is painted in one method but not in the other. Since the number of ways can be huge, output the number of valid ways modulo a given prime number p.

inputFormat

The input consists of a single line with three integers: n m p, where:

• n is the number of wooden planks;
• m is the number of segments on each plank;
• p is a prime number. You must output the number of valid ways to paint the fence modulo p.

outputFormat

Output a single integer – the number of different ways to paint the fence under the given restrictions, modulo p.

sample

1 1 7

1