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}< \color{normal}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 $ .

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