Bridge Coloring Challenge

You are given a magical challenge. In a mystical world, you are presented with m colors and a series of n levels. In the i^th level, there is a bridge consisting of i units. Each unit has 2 cells (i.e. the bridge has 2×i cells arranged in 2 rows and i columns). You need to color the cells using the given m colors so that adjacent cells (cells sharing a common edge) have different colors.

For each level i:

• First, compute the number of valid colorings of the 2×i grid using the m colors such that adjacent cells have different colors. (Note: in the first column, there are two cells and they must have different colors.)
• Then, multiply this number by (2×i)^m.

For example, when m = 2 and i = 1: there are 2 valid colorings for the single column (choose a color for the top cell and a different color for the bottom cell, which gives 2×1 = 2 ways). Then, multiply by (2×1)² = 4 to get a total of 8.

Let T = m² - 3m + 3. It can be shown that for i ≥ 1 the number of valid colorings for the 2×i grid is:

[ \text{colorings}(i) = m\times (m-1) \times T^{i-1} ]

Your final task is to compute the sum, over all levels from 1 to n, of the value:

[ \text{Answer}_i = \Bigl( m\times (m-1) \times T^{i-1} \Bigr) \times (2i)^{m} ]

Then, you must output the sum of these values modulo p.

Note: The two parts of each level's answer (the valid colorings and the multiplier) are defined as above. In the sample, when m = 2 and i = 1, the answer is 2 × (22) = 8.

If you can compute the final answer, you will be able to leave this strange world!

inputFormat

The input consists of three space-separated integers: m, n, and p, where m is the number of colors, n is the number of levels, and p is the modulus.

outputFormat

Output a single integer: the remainder when the sum of the answers for all levels is divided by p.

sample

2 1 100

8