Description

If a tournament contains a Hamiltonian cycle, then we call this tournament “worth recording.”

Choose uniformly at random from all “worth recording” tournaments with $n$ pairwise distinct vertices.

Find the expected number of Hamiltonian cycles in the chosen tournament.

Since the answer may be too large or lose precision, you only need to output the answer modulo $998244353$.

That is: let the answer be $\frac{q}{p}$. You must output an integer $x$ such that $p x \equiv q \bmod 998244353$ and $0 \leqslant x < 998244353$. It can be proved that such an $x$ exists and is unique.

If no such tournament exists, output -1.

Input Format

One line with a positive integer $n$.

Output Format

Output $n$ lines. On line $i$, print the answer for input $i$.

4

1
-1
1
1

Hint

Sample explanations:

• When $n=1$, there is only one tournament, which is a single vertex.
• When $n=2$, the tournament has only one edge and cannot form a Hamiltonian cycle.
• When $n=3$, there are two “worth recording” tournaments, namely $1\to2\to3\to1$ and $1\to3\to2\to1$, each having exactly $1$ Hamiltonian cycle, so the expected value is $1$.
• When $n=4$, there are many “worth recording” tournaments (too many to list here), but all that satisfy the condition are isomorphic, so the expected value is $1$.

Constraints:

• In test points 1–3, $n \leqslant 7$.
• In test points 4–6, $n \leqslant 10$.
• In test points 7–10, $n \leqslant 1000$.
• In test points 11–16, $n \leqslant 10000$.
• In test points 17–25, $n \leqslant 100000$.

The testdata has a gradient; each test point is worth 4 points.

To avoid constant-factor issues, the last two points have a 2 s time limit.

Terminology:

• Tournament: https://en.wikipedia.org/wiki/Tournament_(graph_theory)
• Hamiltonian cycle: https://en.wikipedia.org/wiki/Hamiltonian_cycle

by oscar

Translated by ChatGPT 5