Description

Find how many different labeled unrooted trees with $n$ vertices satisfy the following condition: for every vertex $x$, there exists a vertex $y$ such that there is an edge between $x$ and $y$, and $|x - y| = 1$. Output the answer modulo $998244353$.

Input Format

One line with one positive integer $n$.

Output Format

One line with one integer, the required answer.

4

4

209

21754876

5

11

6

56

Hint

[Sample Explanation #1]

The $4$ trees in Sample #1 that satisfy the condition are shown in the figure above.

[Constraints]

This problem contains $20$ test points, with $5$ points for each test point.

For all test points, $n$ is a positive integer and $2 \leq n \leq {10}^5$。

Translated by ChatGPT 5