Background

In LIAR GAME, Little E saw an interesting game.

Problem Description

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<y$, the smuggling fails, but because the inspector wrongly accused the smuggler, the inspector must pay the smuggler $y/2$ yen. The game is played in a finite number of rounds. The two players take turns being the smuggler and the inspector.

It can be proven that, under optimal play, in each round the smuggler will use the same strategy, and the inspector will also use the same strategy. Little E wants to know, in a single round, what the optimal strategies of both sides are.

Input Format

One line with a positive integer $n$.

Output Format

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

1

665496236 332748118
332748118 665496236

Hint

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 https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5