P11174 "CMOI R1" Looking For Edge Of Ground / City Planning

 [How to count simple labeled undirected connected graphs on $n$ vertices?](https://www.luogu.com.cn/problem/P4841)$\small\color{white}/42^{\text{nd}}\text{Problem by ArCu}.$ There is an obviously wrong method: enumerate a tree, then add edges on it. You need to compute the sum of squares of the number of times each graph is counted.

Given a positive integer $n$. At first, $\text{ClBe}$ chooses a labeled undirected unrooted tree with $n$ vertices, and colors the edges on the tree white. Then he adds any number of edges to this tree, with the following requirements: * The newly added edges are black undirected edges. * After adding edges, if you ignore the colors, the resulting graph is a simple graph. Next, $\text{ClBe}$ puts all possible results into a set $S$. Obviously, this way of counting connected graphs will count the same graph many times, so $\text{ClBe}$ defines $f(G)$ as follows: in $S$, there are $f(G)$ graphs whose underlying graphs (ignoring edge colors) are the same as $G$ (two graphs $A,B$ are the same means for any edge $(u,v)$, $(u,v)\in A\iff(u,v)\in B$). ($\sum_G$ means summing over all possible graphs $G$.) Obviously, $$\sum_{G}f(G)=n^{n-2}2^\binom{n-1}2$$ So you need to compute $$\sum_{G}f(G)^2$$ Output the answer modulo $998244353$. Unfortunately, for some reasons, the modulus **cannot** be $1004535809$.

One line containing one positive integer $n(0

One line containing one integer, the answer you computed.

$\text{Sample Explanation}:$ The set $S$ contains the following $6$ graphs (an edge weight of $0$ means a white edge, and $1$ means a black edge; a vertex label like $1A$ means this is vertex $1$ of graph $A$):  There are $4$ connected graphs on $3$ vertices:  Ignoring colors, * The ones that are the same as $G$ are $B$. * The ones that are the same as $H$ are $A$. * The ones that are the same as $I$ are $C$. * The ones that are the same as $J$ are $D,E,F$. So the answer is $f(G)^2+f(H)^2+f(I)^2+f(J)^2=1^2+1^2+1^2+3^2=12$. $\text{Details of Subtasks}:$ This problem uses bundled testdata. | $\text{Subtask}$ | $n