407348: GYM102769 H Holy Sequence

Alex is proud of the holy sequence.

Alex thinks that a sequence $$$a_1,a_2,\cdots, a_n$$$ is $$$n$$$-holy if and only if

• For each $$$i \in [1,n]$$$, $$$a_i \in \{1,2,\cdots, n\}$$$ ;
• For each $$$i \in [1,n]$$$, $$$p_i - p_{i-1} \le 1$$$ ($$$p_k = \max\{a_1,a_2,\cdots, a_k\}$$$, $$$p_0=0$$$).

For each $$$t = 1,2, \cdots, n$$$, Alex wants to know $$$$$$ \sum_{p \in S_n} \mathrm{cnt}(p,t)^2, $$$$$$ where $$$S_n$$$ is the set of all $$$n$$$-holy sequences and $$$\mathrm{cnt}(p,t)$$$ is the occurrence number of $$$t$$$ in sequence $$$p$$$.

As the results can be very large, output it modulo $$$m$$$.

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10)$$$. $$$T$$$ test cases follow.

For each test case, the only line contains two integers $$$n\ (1 \le n \le 3000)$$$ and $$$m\ (1 \le m \le 10^9)$$$, where $$$n$$$ is the length of holy sequences and $$$m$$$ is the modulus.

The sum of $$$n$$$ in all test cases doesn't exceed $$$10^4$$$.

For each test case, the output starts with a line containing "Case #x:", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$). The second line contains $$$n$$$ numbers, the answer for each $$$t = 1,2,\cdots, n$$$, modulo $$$m$$$.

2
3 998
10 998

Case #1:
19 7 1
Case #2:
996 713 406 353 206 275 175 936 49 1