← 返回题目列表

Codeforces · 1943/D1

D1. 计数很有趣(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的唯一区别是对 $$$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]$$$.