题目背景

如何对 $n$ 个点的简单有标号无向连通图计数？$\small\color{white}/42^{\text{nd}}\text{Problem by ArCu}.$

有一个显然错误的做法：枚举一棵树，然后在上面加边。

你需要求每张图被统计的次数的平方和。

题目描述

给定正整数 $n$。

一开始，$\text{ClBe}$ 会选定一棵 $n$ 个点的有标号无向无根树，将树上的边染成白色。然后他会在这棵树上加任意多条边，且满足：

• 新加的边是黑色的无向边；
• 加完边后的图忽略边的颜色后是一张简单图。

接下来 $\text{ClBe}$ 会将所有可能得到的结果放到一个集合 $S$ 中。

显然这种统计连通图个数的方法会把一个图算很多遍，所以 $\text{ClBe}$ 定义 $f(G)$：$S$ 中有 $f(G)$ 个图在忽略边的颜色后和 $G$ 相同（两个图 $A,B$ 相同指对于任意一条边 $(u,v)$，$(u,v)\in A\iff(u,v)\in B$）。

（$\sum_G$ 代表对所有可能的图 $G$ 求和。）显然

$$\sum_{G}f(G)=n^{n-2}2^\binom{n-1}2$$

所以你需要求

$$\sum_{G}f(G)^2$$

答案对 $998244353$ 取模。很可惜因为一些原因模数不能取 $1004535809$。

输入格式

一行一个正整数 $n(0<n<2^{25})$。

输出格式

一行一个整数，为你求得的答案。

3

12

4

812

5

223440

107

404390093

提示

$\text{Sample Explanation}:$

集合 $S$ 中包含以下 $6$ 张图（边权为 $0$ 代表白边，为 $1$ 代表黑边，点的编号为 $1A$ 代表这是图 $A$ 的 $1$ 号点）：

$3$ 个点的连通图有 $4$ 种：

忽略颜色后，

• 与 $G$ 相同的有 $B$；
• 与 $H$ 相同的有 $A$；
• 与 $I$ 相同的有 $C$；
• 与 $J$ 相同的有 $D,E,F$；

答案为 $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}:$

本题采用捆绑测试。

$\text{Subtask}$	$n<$	$\text{Score}$
$1$	$10$	$5$
$2$	$500$	$25$
$3$	$1500$	$30$
$4$	$4500$	$5$
$5$	$2^{16}$
$6$	$2^{17}$
$7$	$2^{20}$	$20$
$8$	$2^{25}$	$5$