311165: CF1943D2. Counting Is Fun (Hard Version)

D2. Counting Is Fun (Hard Version)time limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference between the two versions is the constraint on $n$. You can make hacks only if both versions of the problem are solved.

An array $b$ of $m$ non-negative integers is said to be good if all the elements of $b$ can be made equal to $0$ using the following operation some (possibly, zero) times:

• Select two distinct indices $l$ and $r$ ($1 \leq l \color{red}{<} r \leq m$) and subtract $1$ from all $b_i$ such that $l \leq i \leq r$.

You are given two positive integers $n$, $k$ and a prime number $p$.

Over all $(k+1)^n$ arrays of length $n$ such that $0 \leq a_i \leq k$ for all $1 \leq i \leq n$, count the number of good arrays.

Since the number might be too large, you are only required to find it modulo $p$.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three positive integers $n$, $k$ and $p$ ($3 \leq n \leq 3000$, $1 \leq k \leq n$, $10^8 < p < 10^9$) — the length of the array $a$, the upper bound on the elements of $a$ and modulus $p$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^7$, and $p$ is prime.

Output

For each test case, on a new line, output the number of good arrays modulo $p$.

ExampleInput

4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353

Output

4
7
10
456615865

Note

In the first test case, the $4$ good arrays $a$ are:

• $[0,0,0]$;
• $[0,1,1]$;
• $[1,1,0]$;
• $[1,1,1]$.

题目大意：
这是一个难题的较难版本。两个版本之间唯一的不同是关于 n 的限制。只有当问题的两个版本都被解决时，你才能进行黑客攻击。

定义一个由 m 个非负整数组成的数组 b 是“好的”，如果 b 的所有元素可以通过以下操作（可能零次）变为 0：

选择两个不同的索引 l 和 r (1 ≤ l < r ≤ m) 并将所有满足 l ≤ i ≤ r 的 b_i 减 1。

给你两个正整数 n、k 和一个素数 p。

在所有 (k+1)^n 个长度为 n 的数组中，使得 0 ≤ a_i ≤ k 对所有 1 ≤ i ≤ n，计算“好的”数组数量。

由于这个数字可能太大，你只需要找到它模 p 的结果。

输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^3) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个正整数 n、k 和 p (3 ≤ n ≤ 3000, 1 ≤ k ≤ n, 10^8 < p < 10^9) —— 数组 a 的长度、数组元素的上下界和模数 p。

保证所有测试用例的 n^2 之和不超过 10^7，且 p 是素数。

输出：
对于每个测试用例，输出一行，表示“好的”数组数量模 p 的结果。

示例：
输入：
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353

输出：
4
7
10
456615865

注意：
在第一个测试用例中，4 个“好的”数组 a 是：
[0,0,0];
[0,1,1];
[1,1,0];
[1,1,1]。题目大意： 这是一个难题的较难版本。两个版本之间唯一的不同是关于 n 的限制。只有当问题的两个版本都被解决时，你才能进行黑客攻击。 定义一个由 m 个非负整数组成的数组 b 是“好的”，如果 b 的所有元素可以通过以下操作（可能零次）变为 0： 选择两个不同的索引 l 和 r (1 ≤ l < r ≤ m) 并将所有满足 l ≤ i ≤ r 的 b_i 减 1。 给你两个正整数 n、k 和一个素数 p。 在所有 (k+1)^n 个长度为 n 的数组中，使得 0 ≤ a_i ≤ k 对所有 1 ≤ i ≤ n，计算“好的”数组数量。 由于这个数字可能太大，你只需要找到它模 p 的结果。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^3) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含三个正整数 n、k 和 p (3 ≤ n ≤ 3000, 1 ≤ k ≤ n, 10^8 < p < 10^9) —— 数组 a 的长度、数组元素的上下界和模数 p。 保证所有测试用例的 n^2 之和不超过 10^7，且 p 是素数。 输出： 对于每个测试用例，输出一行，表示“好的”数组数量模 p 的结果。 示例： 输入： 4 3 1 998244853 4 1 998244353 3 2 998244353 343 343 998244353 输出： 4 7 10 456615865 注意： 在第一个测试用例中，4 个“好的”数组 a 是： [0,0,0]; [0,1,1]; [1,1,0]; [1,1,1]。