Counting Desert Graphs

A cactus graph is an undirected connected graph with no self‐loops or multiple edges in which every edge belongs to at most one simple cycle. In other words, every biconnected component is either an edge or a simple cycle. A desert is an undirected graph all of whose maximal connected components are cactus graphs. (Note that an isolated vertex is considered connected.)

You are given an integer n. How many different deserts are there on n labeled vertices? Since the answer can be very large, output it modulo $$998244353.$$

Remark. A cactus graph always has the property that if you add an extra edge to a spanning tree the unique cycle formed will use each tree edge at most once. In fact, every connected cactus graph G on n vertices can be decomposed into:

• a tree on n vertices (counted by Cayley’s formula: \(n^{n-2}\)); and
• possibly additional edges that create cycles. Any extra edge added to a tree produces a unique cycle. However, in a cactus graph no tree edge may lie in more than one cycle.

One may show that if we denote by \(d(n)\) the number of connected cactus graphs on n vertices then for n ≥ 2 we have

[ \begin{aligned} d(1)&=1,\ d(n)&=n^{n-2}+ \sum_{l=3}^{n-1}; \binom{n}{l} \cdot \frac{(l-1)!}{2} \cdot \Bigl(l\cdot n^{n-l-1}\Bigr) + \begin{cases}0,& n<3,\ \frac{(n-1)!}{2},& n\ge3, \end{cases} \end{aligned} ]

Then the total number of deserts on n vertices is obtained by “exponentiating” the connected case. More precisely, if we define \(F(n)\) as the number of deserts on n labeled vertices (with the convention that \(F(0)=1\)), one may show that the following recurrence holds for n ≥ 1:

[ F(n)=\sum_{s=1}^{n};\binom{n-1}{s-1} ; d(s) ; F(n-s). ]

Your task is to compute \(F(n)\) modulo 998244353.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ N). (N is such that the answer can be computed within the time limits.)

outputFormat

Output a single integer: the number of deserts on n labeled vertices modulo 998244353.

sample

1

1