#P1943D2. Counting Is Fun (Hard Version)
Counting Is Fun (Hard Version)
Description
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$.
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.
For each test case, on a new line, output the number of good arrays 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$.
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
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]$.