P9142 [THUPC 2023 Preliminary] Fraud Game

In *LIAR GAME*, Little E saw an interesting game.

This game is called *Smuggling Game*. The rules are roughly as follows: one player plays the smuggler, and the other player plays the inspector. The smuggler can secretly put $x$ yen into a box ($x$ is an integer in $[0,n]$, chosen by the smuggler), and the inspector needs to guess the amount in the box. Suppose the inspector guesses $y$ (and $y$ must also be an integer). If $x=y$, the smuggling fails, and the smuggler gets nothing. If $x>y$, the smuggling succeeds, and the smuggler can take $x$ yen from the inspector. If $x

One line with a positive integer $n$.

Output two lines, each containing $n+1$ numbers. The $i$-th number represents the probability of placing/guessing $i-1$ yen. Output the smuggler's strategy on the first line, and the inspector's strategy on the second line. You need to guarantee that, when one side's strategy remains unchanged, the other side cannot increase their expected payoff by changing their strategy in any way. It can be proven that such strategies are unique. Output the answer modulo $998244353$.

#### Sample Explanation 1 These $4$ numbers are $2/3,1/3,1/3,2/3$. #### Subtasks Constraints: $1\le n \le 400000$. #### Source From the preliminary round of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2023). Resources such as the editorial can be found at . Translated by ChatGPT 5