方差

题目描述 对于一棵 𝑛𝑛 个点的带标号无根树，设 𝑑𝑑𝑖𝑖 为点 𝑖𝑖 的度数。定义一棵树的方差为数组 𝑑𝑑1 , 𝑑𝑑2 , … , 𝑑𝑑𝑛𝑛 的方差。

给定 𝑛𝑛 ，求所有带标号的 𝑛𝑛 个点的无根树的方差之和。

你需要将答案对 998244353 取模，也就是如果答案表示成最简分数𝑝𝑝/𝑞𝑞，输出 𝑝𝑝 ⋅ 𝑞𝑞 −1 mod 998244353。

输入格式 第一行一个整数𝑛𝑛。

输出格式 一个整数，表示答案。

样例输入 1 3

样例输出 1 665496236

样例输入 2 114514

样例输出 2 134842286

数据规模 共 10 个测试点。

测试点1满足𝑛𝑛 ≤ 5。

测试点2,3满足𝑛𝑛 ≤ 10。

测试点4,5满足𝑛𝑛 ≤ 500。

测试点6,7满足𝑛𝑛 ≤ 3000。

对于所有数据，满足2 ≤ 𝑛𝑛 ≤ 106 。