Background

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

Problem Description

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$.

Input Format

One line with one integer $n$.

Output Format

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

3

8

Hint

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