P8923 『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 不会了。为了不让你看出来他根本就不会，他随便写了一个数据范围就把这题扔给你做了。 现在压力来到了你这边，你能否顺利切掉这个题呢？

无

无

对于 $100\%$ 的数据，$1\le n\le 5\times 10^3$，$1\le m\le 10^9$，$10^9