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

输入 #1

3
2 2 101
5 1 999999937
100 23190 3214373

输出 #1

57
225
2347147