Gnutella Chessmaster

Time limit3sMemory limit512 MB

Summary

Count the non-attacking bishop placements on an n by n board for each bishop count k from 1 to 2n-1, modulo 998244353.

Level: Hard9 of 10
Topics: Combinatorics, Math, Divide and conquer, Dynamic programming
Solved: No attempts yet

Problem

Alexander has recently reached an absurdly high rating on the Chessforces competition website. His coach gave him a hard problem so that he could truly prove his skill.

Consider an $n \times n$ chessboard. A bishop is a chess piece that attacks all positions sharing a diagonal with it. A non-attacking configuration is an arrangement of several bishops on the chessboard in which no two bishops occupy the same position and no bishop attacks another.

Alexander has to count the number of non-attacking configurations with exactly $k$ bishops for each $k$ from $1$ to $2n - 1$ . The answers can be large, so each number is taken modulo $998\,244\,353$ , a completely random number.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 10^5$ ).

Output

Print $2n - 1$ integers. The $k$ -th integer is the number of non-attacking configurations of exactly $k$ bishops on an $n \times n$ chessboard, modulo $998\,244\,353$ .

Examples3

Example 1
Input
```
2
```
Expected output
```
4 4 0
```
Example 2
Input
```
3
```
Expected output
```
9 26 26 8 0
```

Example 3

Input

Expected output

100 4380 110960 1809464 20014112 154215760 837543200 214861037 625796024 941559921 770927213 837612209 756883449 146369278 295974400 17275136 246784 1024 0