如果每条边的权重是 $$$1$$$ 或 $$$-1$$$,并且对于每个顶点 $$$i$$$,以 $$$i$$$ 作为一个端点的所有边的边权重的乘积为$$$-1$$$。
给你一个正整数$$$n$$$。有 $$$n^{n-2} \cdot 2^{n-1}$$$ 不同的$$$^\dagger$$$ 边加权树,其 $$$n$$$ 顶点编号从 $$$1$$$ 到 $$$n$$$,这样每条边要么是 $$$1$$$ 要么是 $$$-1$$$。你的任务是找到所有这样的好树的 $$$d(1,n)^\ddagger$$$ 的总和。由于答案可能相当大,因此您只需对 $$$998\,244\,353$$$ 求模即可。
$$$^\dagger$$$ 如果出现以下任一情况,则认为两棵树是不同的:
- 存在两个顶点,其中一棵树中它们之间有一条边,而另一棵树中则没有边。
- 存在两个顶点,两棵树中它们之间都有一条边,但一棵树中它们之间的边的权重与另一棵树中的不同。
请注意,根据凯莱公式,$$$n$$$ 标记顶点上的树数量为 $$$n^{n-2}$$$。由于我们有 $$$n-1$$$ 边,因此存在 $$$2^{n-1}$$$ 可能的权重分配(权重可以是 $$$1$$$ 或 $$$-1$$$)。这就是为什么不同边加权树的总数为 $$$n^{n-2} \cdot 2^{n-1}$$$。
$$$^\ddagger$$$ $$$d(u,v)$$$ 表示从 $$$u$$$ 到 $$$v$$$ 的唯一简单路径上所有边的权重之和。
输入
输入的第一行也是唯一一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$)。
输出
唯一的输出行应包含一个整数,即所需的答案,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2
输出 #1
998244352
输入 #2
1
输出 #2
0
输入 #3
4
输出 #3
998244343
输入#4
10
输出#4
948359297
输入 #5
43434
输出 #5
86232114
注意
在第一个测试用例中,只有 $$$1$$$ 不同的好树。该树的 $$$d(1,2)$$$ 值为 $$$-1$$$,模 $$$998\,244\,353$$$ 后为 $$$998\,244\,352$$$。
在第二个测试用例中,任何树的 $$$d(1,1)$$$ 的值为 $$$0$$$,因此答案为 $$$0$$$。
在第三个测试用例中,有 $$$16$$$ 不同的好树。 $$$d(1,4)$$$ 的值为:
- $$$-2$$$ 为 $$$2$$$ 树;
- $$$-1$$$ 为 $$$8$$$ 树;
- $$$0$$$ 为 $$$4$$$ 树;
- $$$1$$$ 为 $$$2$$$ 树。
所有树的 $$$d(1,4)$$$ 之和为 $$$2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10$$$,模数下为 $$$998\,244\,343$$$ $$$998\,244\,353$$$。