← 返回题目列表

Codeforces · 1943/D2

D2. 计数很有趣(困难版)

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

这是问题的困难版本。两个版本之间的唯一区别是对 $$$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 3000$$$, $$$1 \leq k \leq n$$$, $$$10^8 < p < 10^9$$$) — 数组的长度 $$$a$$$, $$$a$$$ 元素和模 $$$p$$$ 的上限。

保证所有测试用例的$$$n^2$$$之和不超过$$$10^7$$$,且$$$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]$$$.