P8923 "MdOI R5" Many Minimizations

This problem is not a polynomial problem. It is recommended to solve E first. [](https://postimg.cc/xcrKn6Pg)

Little L ran into a classic problem: given an **integer** sequence $a$ of length $n$, you need to choose a **non-decreasing** **real-valued** sequence as $b$ among all such sequences, to minimize $\sum\limits_{i=1}^n |a_i-b_i|$. It can be proven that the answer is an integer. He solved it instantly: isn't this just the isotonic regression template? He felt the problem was too easy, so he decided to make it harder: For all **integer** sequences $a$ of length $n$ satisfying $\forall i\in[1,n],a_i\in[1,m]$, compute the sum of the answers to the problem above, modulo the **prime** $p$. Here $n,m,p$ are given constants. Now Little L could not do it anymore. To avoid letting you see that he actually could not do it at all, he casually wrote down some constraints and threw the problem to you. Now the pressure is on you. Can you solve this problem successfully?

There is one line containing three integers, representing $n,m,p$ in order.

There is one line containing one integer, representing the answer.

For $100\%$ of the testdata, $1\le n\le 5\times 10^3$, $1\le m\le 10^9$, $10^9