Background

How to count simple labeled undirected connected graphs on $n$ vertices?$\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.

Problem Description

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,

So you need to compute

Output the answer modulo $998244353$. Unfortunately, for some reasons, the modulus cannot be $1004535809$.

Input Format

One line containing one positive integer $n(0<n<2^{25})$.

Output Format

One line containing one integer, the answer you computed.

3

12

4

812

5

223440

107

404390093

Hint

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

Translated by ChatGPT 5