18972번 - Gnutella Chessmaster 다국어

문제

Alexander has recently achieved ridiculously high rating on Chessforces competition website. Alexander's coach challenged him with a difficult problem so that Alexander could truly prove his mettle.

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 such that no two bishops occupy the same position, and no bishop attacks any other.

Alexander has to count the number of non-attacking bishop configurations with exactly $k$ bishops for each $k$ from 1ドル$ to 2ドルn - 1$. Since the answers can be large, each number has to be computed modulo a completely random number 998ドル,244円,353円$.

입력

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

출력

Print 2ドルn - 1$ integers. The $k$-th of these integers should be the number (modulo 998ドル,244円,353円$) of non-attacking configurations of exactly $k$ bishops on an $n \times n$ chessboard.

제한

힌트