考虑一个有 $n$ 个顶点的无向图，顶点编号为 $1$ 到 $n$，每个顶点都被染成红色或黑色。如果一个图满足以下两个条件，则称其是优美的（beautiful）：
- 删去所有两端点均为红色的边后，图是一棵树；
- 删去所有两端点均为黑色的边后，图是一棵树。
如果一个图是优美的，且其边数不小于任何其他具有相同顶点数的优美图的边数，则称该图是最优的（best）。
你的任务是计算具有 $n$ 个顶点的最优图的数量。如果两个图的边集不同，或者至少一个顶点的颜色不同，或者两者皆有，则认为这两个图是不同的。由于答案可能很大，请将其对 $998\,244\,353$ 取模后输出。
输入格式
仅包含一行，一个整数 $n$ ($2 \le n \le 10^6$)。
输出格式
输出一个整数，表示具有 $n$ 个顶点的最优图的数量，对 $998\,244\,353$ 取模。
样例
输入样例 1
3
输出样例 1
6
输入样例 2
4
输出样例 2
12
输入样例 3
5
输出样例 3
240
输入样例 4
6
输出样例 4
1080