P7275 Count Trees

Find how many different labeled unrooted trees with $n$ vertices satisfy the following condition: for every vertex $x$, there exists a vertex $y$ such that there is an edge between $x$ and $y$, and $|x - y| = 1$. Output the answer modulo $998244353$.

One line with one positive integer $n$.

One line with one integer, the required answer.

**[Sample Explanation #1]**  The $4$ trees in Sample #1 that satisfy the condition are shown in the figure above. ---- **[Constraints]** This problem contains $20$ test points, with $5$ points for each test point. | Test point ID | Range of $n$ | | :-----------: | :----------: | | $1 \sim 2$ | $\leq 7$ | | $3 \sim 4$ | $\leq 14$ | | $5 \sim 8$ | $\leq 30$ | | $9 \sim 12$ | $\leq 10^3$ | | $13 \sim 20$ | $\leq 10^5$ | For all test points, $n$ is a positive integer and $2 \leq n \leq {10}^5$。 Translated by ChatGPT 5