Counting Weakly Connected Directed Acyclic Graphs

Given n labeled vertices, count the number of directed acyclic graphs (DAGs) that are weakly connected.

A directed acyclic graph is one that has no directed cycle. A graph is said to be weakly connected if, when all the directed edges are replaced by undirected edges, the resulting undirected graph is connected.

The answer can be expressed using the following recurrences. Let \(\mathcal{A}(n)\) be the total number of DAGs on \(n\) vertices. It satisfies:

\[ \mathcal{A}(n) = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} 2^{k(n-k)} \mathcal{A}(n-k), \quad \mathcal{A}(0)=1. \]

Let \(\mathcal{C}(n)\) be the number of weakly connected DAGs. Then, by inclusion–exclusion, we have:

\[ \mathcal{C}(n) = \mathcal{A}(n) - \sum_{k=1}^{n-1} \binom{n-1}{k-1} \mathcal{C}(k) \mathcal{A}(n-k). \]

Output the value of \(\mathcal{C}(n)\) modulo \(998244353\).

inputFormat

The input consists of a single integer n representing the number of vertices.

\(1 \leq n\leq \text{(small constraint)}\)

outputFormat

Output a single integer, the number of weakly connected directed acyclic graphs on n vertices modulo \(998244353\).

sample

1

1