P5900 Counting Unlabeled Unrooted Trees

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

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

Input one line with a positive integer $n$.

Output one line with one integer, representing the answer.

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