这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$n \le 2 \cdot 10^3$$$。只有解决了该问题的所有版本,您才能破解。
进入古老的宫殿“回文宫”,你注意到它的墙壁上有奇特的图案。该图案是大小为 $$$1 \times n$$$ 的马赛克,由鹅卵石制成,每个鹅卵石都涂有 $$$m$$$ 不同颜色之一。
的 正确性 任意马赛克$$$s$$$的 被定义为$$$s$$$中回文的非空子段的数量。的 马赛克的 美女 被定义为它的正方形 正确性 任意马赛克$$$s$$$的。例如,对于马赛克 rgrb,有五个回文子段: r, g, r, b,和 rgr。因此,其 正确性 任意马赛克$$$s$$$的 是 $$$5$$$,其 美女 是 $$$25$$$。
当你漫步在这座宫殿中时,你想知道:这个宫殿的预期价值是多少? 美女 如果每个 $$$n$$$ 鹅卵石的颜色选择统一且独立于其他鹅卵石的颜色?打印对素数 $$$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 \lt p \lt 10^9$$$) 表示马赛克的长度,不同颜色的鹅卵石的数量,以及需要计算答案的模数。
保证 $$$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$$$ 的整数。换句话说,输出这样一个整数$$$t$$$,即$$$0 \le t \lt x$$$ 和$$$t \cdot z \equiv y \pmod{x}$$$。
示例
输入复制
32 2 1015 1 999999937100 23190 3214373
输出复制
572252347147
注意
在第一个测试用例中,如果只能使用两种不同颜色的鹅卵石来构造它们,则总共有四个长度为 $$$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 的马赛克的所有子段都将是回文。