P5434 Counting Labeled Deserts

As everyone knows, counting cacti is a very easy counting problem, so we are going to make it harder.jpg.

A cactus is an undirected connected graph. In a cactus, any edge appears in at most one cycle. Also, in the cactus defined in this problem, the cactus must have **no multiple edges** and **no self-loops**. A desert is an undirected graph in which every maximal connected component is a cactus. --- Given an integer $n$, find how many different deserts with $n$ vertices there are (the vertices are labeled). Since the answer may be very large, you only need to output it modulo $998244353$.

One line with one integer $n$.

One line with one integer, the answer modulo $998244353$.

For the sample, all possible cases are as follows:  You can see that there are no more deserts. --- Constraints: For $30\%$ of the testdata: $n\leqslant5000$. For $100\%$ of the testdata: $3\leqslant n\leqslant100000$. Translated by ChatGPT 5