Background

This problem is not a polynomial problem. It is recommended to solve E first.

Problem Description

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?

Input Format

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

Output Format

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

3 2 1000000007

4

5 5 1000000007

11040

50 50 1000000009

875463033

Hint

For $100\%$ of the testdata, $1\le n\le 5\times 10^3$, $1\le m\le 10^9$, $10^9<p\le 1.01\times 10^9$, and $p$ is guaranteed to be prime.

$\operatorname{Subtask} 1(10\%)$: $n,m\le 7$.

$\operatorname{Subtask} 2(10\%)$: $m\le 2$.

$\operatorname{Subtask} 3(10\%)$: $n,m\le 50$.

$\operatorname{Subtask} 4(10\%)$: $n\le 50$.

$\operatorname{Subtask} 5(10\%)$: $n,m\le 500$.

$\operatorname{Subtask} 6(10\%)$: $n\le 500$.

$\operatorname{Subtask} 7(10\%)$: $m\le 5\times 10^3$.

$\operatorname{Subtask} 8(30\%)$: no special constraints.

Sample Explanation 1

There are the following $8$ possible cases:

$a=(1,1,1),b=(1,1,1),ans=0$.

$a=(1,1,2),b=(1,1,2),ans=0$.

$a=(1,2,1),b=(1,1,1),ans=1$.

$a=(1,2,2),b=(1,2,2),ans=0$.

$a=(2,1,1),b=(1,1,1),ans=1$.

$a=(2,1,2),b=(1,1,2),ans=1$.

$a=(2,2,1),b=(2,2,2),ans=1$.

$a=(2,2,2),b=(2,2,2),ans=0$.

Therefore the answer is $0+0+1+0+1+1+1+0=4$.

Note that for a fixed $a$, the optimal $b$ is not necessarily unique. Only one possible solution is shown above.

$\operatorname{Bonus}$: achieve $O(n\log n)$ when $p$ is an NTT modulus. In fact, based on the intended solution of this problem, this part is not difficult.

Translated by ChatGPT 5