P6128 [CF2018F3] Speedbreaker Counting (Hard Version)
NOI
题目描述

This is the hard version of the problem. In the three versions, the constraints on $n$ and the time limit are different. You can make hacks only if all the versions of the problem are solved.

This is the statement of Problem D1B:

  • There are $n$ cities in a row, numbered $1, 2, \ldots, n$ left to right. At time $1$, you conquer exactly one city, called the starting city. At time $2, 3, \ldots, n$, you can choose a city adjacent to the ones conquered so far and conquer it. You win if, for each $i$, you conquer city $i$ at a time no later than $a_i$. A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?

For each $0 \leq k \leq n$, count the number of arrays of positive integers $a_1, a_2, \ldots, a_n$ such that

  • $1 \leq a_i \leq n$ for each $1 \leq i \leq n$;
  • the answer to Problem D1B is $k$.

The answer can be very large, so you have to calculate it modulo a given prime $p$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3000$). The description of the test cases follows.

The only line of each test case contains two integers $n$, $p$ ($1 \le n \le 3000$, $10^8 \leq p \leq 10^9$, $p$ is prime) — the number of cities and the modulo.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

Output

For each test case, output $n+1$ integers: the $i$-th integer should be the number of arrays that satisfy the conditions for $k = i-1$.

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
11 1 998244353 2 998244353 3 998244353 4 998244353 5 998244353 6 998244353 7 998244353 8 998244353 9 998244353 10 102275857 10 999662017
样例输出
0 1 1 2 1 14 7 4 2 183 34 19 16 4 2624 209 112 120 48 12 42605 1546 793 992 468 216 36 785910 13327 6556 9190 4672 2880 864 144 16382863 130922 61939 94992 50100 36960 14256 4608 576 382823936 1441729 657784 1086596 583344 488700 216000 96480 23040 2880 20300780 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400 944100756 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400
提示

In the first test case,

  • arrays with $1$ good starting city: $[1]$.

In the second test case,

  • arrays with $0$ good starting cities: $[1, 1]$;
  • arrays with $1$ good starting city: $[1, 2]$, $[2, 1]$;
  • arrays with $2$ good starting cities: $[2, 2]$.

In the third test case,

  • arrays with $0$ good starting cities: $[1, 1, 1]$, $[1, 1, 2]$, $[1, 1, 3]$, $[1, 2, 1]$, $[1, 2, 2]$, $[1, 3, 1]$, $[1, 3, 2]$, $[2, 1, 1]$, $[2, 1, 2]$, $[2, 2, 1]$, $[2, 2, 2]$, $[2, 3, 1]$, $[2, 3, 2]$, $[3, 1, 1]$;
  • arrays with $1$ good starting city: $[1, 2, 3]$, $[1, 3, 3]$, $[2, 1, 3]$, $[3, 1, 2]$, $[3, 1, 3]$, $[3, 2, 1]$, $[3, 3, 1]$;
  • arrays with $2$ good starting cities: $[2, 2, 3]$, $[2, 3, 3]$, $[3, 2, 2]$, $[3, 3, 2]$;
  • arrays with $3$ good starting cities: $[3, 2, 3]$, $[3, 3, 3]$.