CF1943D2 Counting Is Fun (Hard Version)

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}{

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 $ .

In the first test case, the $ 4 $ good arrays $ a $ are: - $ [0,0,0] $ ; - $ [0,1,1] $ ; - $ [1,1,0] $ ; - $ [1,1,1] $ .