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