「CMOI R1」Looking For Edge Of Ground／City Planning

 [如何对 $n$ 个点的简单有标号无向连通图计数？](https://www.luogu.com.cn/problem/P4841)$\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}$ | $5$ | | $6$ | $2^{17}$ | $5$ | | $7$ | $2^{20}$ | $20$ | | $8$ | $2^{25}$ | $5$ |