Background

Considering that Luogu does not have this type of problem yet, here is a simple easy problem.

Problem Description

Find the number of unlabeled unrooted trees with $n$ nodes. Output the answer modulo $998244353$.

Input Format

Input one line with a positive integer $n$.

Output Format

Output one line with one integer, representing the answer.

7

11

27

751065460

Hint

Constraints
For $30\%$ of the testdata, $1\le n \le 1000$;
For $100\%$ of the testdata, $1\le n \le 2\times 10^5$.

Although $\Theta(n \log^2 n)$ can also pass, it is not very meaningful. It is recommended to implement a $\Theta(n \log n)$ solution.

Translated by ChatGPT 5