Problem Description

Given an integer \( n \), count the number of unlabeled rootless trees with \( n \) nodes, and output the result modulo \( 998244353 \).

Input Format

A single line containing a positive integer \( n \).

Output Format

A single line containing an integer representing the answer.

Sample Input and Output

Sample Input #1

7

Sample Output #1

11

Sample Input #2

27

Sample Output #2

751065460

Notes

Data Range:
- For 30% of the test cases, \( 1 \leq n \leq 1000 \).
- For 100% of the test cases, \( 1 \leq n \leq 2 \times 10^5 \).

Although an algorithm with time complexity \( \Theta(n \log^2 n) \) can pass, it is not meaningful. It is recommended to implement an algorithm with time complexity \( \Theta(n \log n) \).

见题面 Input 部分

见题面 Output 部分