A16529. Beautiful Patterns (Easy Version)

这是该题目的简单版本，不同版本的区别在于本题满足 $n \le 2 \cdot 10^3$。你只有在解决了本题所有版本后才能进行 hack。

进入古老的“回文宫殿”后，你注意到墙上有奇特的图案。图案是一块大小为 $1 \times n$ 的马赛克，由 $n$ 个小石子组成，每个小石子的一面涂成 $m$ 种颜色中的一种。

一个马赛克 $s$ 的正确性被定义为其所有非空回文子段的数量。马赛克的美丽度被定义为其正确性的平方。例如，对于马赛克 “rgrb”，共有五个回文子段：r、g、r、b 和 rgr。因此，其正确性为 $5$，美丽度为 $25$。

在游览宫殿时，你产生了这样的思考：如果每个小石子的颜色都是在 $m$ 种颜色中独立等概率选取的，那么这个马赛克的美丽度的期望值是多少？请输出该期望值对素数 $p$ 取模后的结果。

每组测试输入包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 1000$）。接下来每个测试用例一行，包含三个整数 $n$、$m$ 与 $p$（$1 \leq n \leq 2 \cdot 10^3$，$1 \leq m \leq 10^7$，$m < p < 10^9$），分别表示马赛克的长度、小石子的颜色种类数，以及结果需要取模的素数 $p$。

保证 $p$ 是素数。并且所有测试用例中 $n$ 之和不超过 $2 \cdot 10^3$。

对于每个测试用例，输出该马赛克美丽度的期望值对 $p$ 取模后的结果。

更形式化地，令 $x = p$。可以证明，答案可以表示成一个既约分数 $\frac{y}{z}$，其中 $y$、$z$ 为整数且 $z \not\equiv 0 \pmod{x}$。你需要输出 $y \cdot z^{-1} \bmod x$，即 $0 \le t < x$ 且 $t \cdot z \equiv y \pmod{x}$ 的整数 $t$。

在第一个测试用例里，长度为 $2$ 的马赛克共有四种可能（当每个小石子可以用两种颜色构成时），其中两种有两段回文子段，另外两种各有三段。因此其美丽度的期望为 $\left(\frac{2^2}{4} + \frac{2^2}{4} + \frac{3^2}{4} + \frac{3^2}{4}\right) = 13 \cdot 2^{-1} \bmod 101 = 57$。

在第二个测试用例里，长度为 $5$ 的马赛克的所有子段均为回文。