B'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: 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 <= q a_i <= q k for all 1 <= q i <= q 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 <= q t <= q 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 <= q n <= q 3000 , 1 <= q k <= q 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: '...