P4599 [HEOI2012] Zhaozhou Bridge

fyg carried his computer to Hebei just to catch a glimpse of the ancient Zhaozhou Bridge. At last, he arrived at Zhaozhou Bridge, set down his computer, and was about to rest. A gust of wind blew, and a figure flashed out of it. fyg felt the world spin; when he opened his eyes again, he found himself in a magical realm, standing on a giant disk. Looking around, there were strange bridges everywhere, and not far away an old man was sitting cross-legged.

While fyg was still amazed, the old man (could it be the legendary Mr. Zhang who once crossed Zhaozhou Bridge?!) began to speak: Mortal, you are now in my world. If you want to leave, you must answer my question. fyg nodded, and the old man continued: You are going to clear a series of levels. I give you $m$ colors, and there are $n$ levels in total (even immortals know math—what pressure...). In each level, there is a bridge. In level $i$, the bridge has length $i$ units, and each unit length has $2$ cells (that is, the bridge has $2i$ cells). Now you need to compute: the number of ways to color this bridge so that adjacent cells have different colors, then multiply it by $(2 \times i)^m$. For example, in level $1$, if you have $2$ colors, blue and green, then the final number would be $2 \times 2 \times 2 = 8$; the number of coloring schemes is $2$ (as shown in the figure; rotations and reflections are counted as different), and then you also multiply by two 2s. After you come out, I will ask you for the sum of the numbers computed for all levels. If you answer correctly, I will let you go; otherwise, you will be trapped in an endless cycle.  fyg thought the problem was too trivial and did not want to compute it at all... So he immediately opened his computer, logged into QQ, and found you, who enjoy calculations, asking you to directly compute the final answer and help him return to Zhaozhou Bridge. These two numbers can both be very large, and fyg does not want to make it hard for you, so you only need to tell him the remainder when divided by $p$.

A single line containing three positive integers $n$, $m$, and $p$, separated by spaces. The meanings of $n$, $m$, and $p$ are as described in the problem statement.

One line, the remainder of the sum of the values modulo $p$.

### Sample Explanation There are $2$ levels in total. - In the first level, the bridge length is $1$, there are $2$ cells in total, the number of coloring schemes is $20$, then multiply by $2^5$, and the number computed for the first level is $640$. - In the second level, the bridge length is $2$, there are $4$ cells in total, the number of coloring schemes is $260$, then multiply by $4^5$, and the number computed for the second level is $266240$. The sum of the two numbers leaves a remainder $30$ when divided by $50$, so the output is $30$. ### Constraints - For 25% of the testdata, $n \leq 10^6$, $m \leq 200$, $p \leq 10^9$. - For 40% of the testdata, $n \leq 10^9$, $m \leq 120$, $p \leq 10^9$. - For 15% of the testdata, $n \leq 10^9$, $m \leq 200$, $p \leq 10^9$. - For the final 20% of the testdata, $n \leq 10^9$, $m \leq 3000$, $p \leq 3000$. HEOI 2012 Day2 Task1. Translated by ChatGPT 5