Slime and Sequences (Easy Version)

2000ms

262144K

Description:

Note that the only differences between easy and hard versions are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences $$$p$$$ of length $$$n$$$ as follows:

For each $$$k>1$$$ that presents in $$$p$$$, there should be at least one pair of indices $$$i,j$$$, such that $$$1 \leq i < j \leq n$$$, $$$p_i = k - 1$$$ and $$$p_j = k$$$.

For the given integer $$$n$$$, the set of all good sequences of length $$$n$$$ is $$$s_n$$$. For the fixed integer $$$k$$$ and the sequence $$$p$$$, let $$$f_p(k)$$$ be the number of times that $$$k$$$ appears in $$$p$$$. For each $$$k$$$ from $$$1$$$ to $$$n$$$, Slime wants to know the following value:

$$$$$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353$$$$$$

Input:

The first line contains one integer $$$n\ (1\le n\le 5000)$$$.

Output:

Print $$$n$$$ integers, the $$$i$$$-th of them should be equal to $$$\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353$$$.

Sample Input:

Sample Output:

3 1

Sample Input:

Sample Output:

10 7 1

Sample Input:

Sample Output:

Note:

In the first example, $$$s=\{[1,1],[1,2]\}$$$.

In the second example, $$$s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}$$$.

In the third example, $$$s=\{[1]\}$$$.

Informação

Provedor Codeforces

Código CF1349F1