Description

Count the number of labeled directed acyclic graphs (DAGs) on $n$ vertices with the requirement that the graph is weakly connected (that is, after replacing all directed edges with undirected edges, the resulting graph is connected). Output the answer modulo $998244353$.

Input Format

An integer $T$.

Output Format

There are $T$ lines. On the $i$-th line $(1\le i\le T)$, output the answer when $n=i$.

5

1
2
18
446
26430

Hint

The first test point has $T = 2000$.

The second test point has $T = 100000$.

Translated by ChatGPT 5