题目背景

本题不是多项式题，建议先做 E。

题目描述

小 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$。

输出格式

共一行，一个整数，表示答案。

3 2 1000000007

4

5 5 1000000007

11040

50 50 1000000009

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)$。实际上在本题正解的基础上这一部分并不困难。