这是问题的简单版本。两个版本之间的唯一区别是对 $$$n$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
如果 $$$b$$$ 的所有元素可以使用以下操作几次(可能是零次)等于 $$$0$$$,则 $$$m$$$ 非负整数的数组 $$$b$$$ 被认为是好的:
- 选择两个不同的索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \color{red}{<} r \leq m$$$) 并从所有 $$$b_i$$$ 中减去 $$$1$$$,这样 $$$l \leq i \leq r$$$。
给你两个正整数 $$$n$$$、$$$k$$$ 和一个质数 $$$p$$$。
在所有长度为 $$$n$$$ 的 $$$(k+1)^n$$$ 数组中,对于所有 $$$1 \leq i \leq n$$$,$$$0 \leq a_i \leq k$$$,计算好数组的数量。
由于数字可能太大,您只需对 $$$p$$$ 求模即可。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个正整数 $$$n$$$、$$$k$$$ 和 $$$p$$$ ($$$3 \leq n \leq 400$$$, $$$1 \leq k \leq n$$$, $$$10^8 < p < 10^9$$$) — 数组 $$$a$$$ 的长度, $$$a$$$ 和模 $$$p$$$ 元素的上限。
保证所有测试用例的 $$$n^2$$$ 之和不超过 $$$2 \cdot 10^5$$$,且 $$$p$$$ 为素数。
输出
对于每个测试用例,在新行中输出对 $$$p$$$ 取模的良好数组的数量。
示例
输入 #1
4 3 1 998244853 4 1 998244353 3 2 998244353 343 343 998244353
输出 #1
4 7 10 456615865
注意
在第一个测试用例中,$$$4$$$ 好的数组 $$$a$$$ 是:
- $$$[0,0,0]$$$;
- $$$[0,1,1]$$$;
- $$$[1,1,0]$$$;
- $$$[1,1,1]$$$.