『MdOI R5』Many Minimizations
题目背景
本题不是多项式题，建议先做 E。
[](https://postimg.cc/xcrKn6Pg)
题目描述
小 L 遇到了一个经典题：给定一个长度为 $n$ 的**整数**序列 $a$，你需要在所有**单调不降**的**实数**序列中选出一个作为 $b$，最小化 $\sum\limits_{i=1}^n |a_i-b_i|$。可以证明答案是整数。
他一眼就秒了这个题：这不是保序回归板子吗！
他觉得这题太水了，于是决定加强一下：
对于所有长度为 $n$ 的且满足 $\forall i\in[1,n],a_i\in[1,m]$ 的**整数**序列 $a$，求出上面这个问题的答案的总和对**质数** $p$ 取模后的结果。其中 $n,m,p$ 是给定的常数。
这下小 L 不会了。为了不让你看出来他根本就不会，他随便写了一个数据范围就把这题扔给你做了。
现在压力来到了你这边，你能否顺利切掉这个题呢？
输入输出格式
输入格式
共一行，三个整数，依次表示 $n,m,p$。
输出格式
共一行，一个整数，表示答案。
输入输出样例
输入样例 #1
3 2 1000000007输出样例 #1
4输入样例 #2
5 5 1000000007输出样例 #2
11040输入样例 #3
50 50 1000000009输出样例 #3
875463033说明
对于 $100\%$ 的数据，$1\le n\le 5\times 10^3$，$1\le m\le 10^9$，$10^9<p\le 1.01\times 10^9$，保证 $p$ 是质数。
$\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\%)$：无特殊限制。
#### 样例说明 1
有以下 $8$ 种可能的情况：
$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$。
因此答案为 $0+0+1+0+1+1+1+0=4$。
注意，对于一个固定的 $a$，最优的 $b$ 不一定唯一。上面只给出了一种可能的解。
$\operatorname{Bonus}$：在 $p$ 为 NTT 模数的情况下做到 $O(n\log n)$。实际上在本题正解的基础上这一部分并不困难。