Description

How many structural isomers (stereoisomers not considered) are there for an alkane with $n$ carbon atoms?

Hint: If you do not know what an alkane is, you can consider this problem equivalent to counting the number of unlabelled unrooted trees with $n$ nodes, where the degree of each node is $\le 4$.

Input Format

An integer $n$ representing the number of carbon atoms.

Output Format

Output an integer representing the answer, taken modulo $998244353$.

5

3

Hint

Explanation for Sample 1

Constraints

For all testdata, it is guaranteed that $1 \le n \le 10^5$.

Translated by ChatGPT 5