Problem Description

Determine the number of distinct labeled unrooted trees with $n$ nodes, such that for any node $x$, there exists a node $y$ such that $x$ and $y$ are connected by an edge and $|x - y| = 1$. The answer should be modulo $998244353$.

Input Format

A single line containing a positive integer $n$.

Output Format

A single line containing an integer, the required answer.

Sample Input and Output

Sample Input #1

4

Sample Output #1

4

Sample Input #2

209

Sample Output #2

21754876

Sample Input #3

5

Sample Output #3

11

Sample Input #4

6

Sample Output #4

56

Notes

[Sample Explanation #1]

The four trees that meet the criteria in Sample #1 are shown in the image above.

[Data Range]

This problem includes 20 test cases, each worth 5 points.

For all test cases, $n$ is a positive integer and $2 \leq n \leq 10^5$.

见题面 Input 部分

见题面 Output 部分