题目描述

二中的校门外有一排树，一共 n 棵。每棵树的高度为 [0,1] 之间的随机小数。每棵树上都有一个苹果。

zjt 把这 n 棵树从左到右编号为 1∼n。zjt 还会在某些树之间挂上绳索。设第 i 棵树的高度为 a_i 。如果对于两棵树 i,j 满足 i<j 且 a_i<a_j ，那么 zjt 就会在第 i 棵树与第 j 棵树之间挂上一条绳索。这些绳索是双向的。

这时，有很多猴子路过了这里，你可以认为是 n 只，或是 2n 只，或是 ∞ 只。这些猴子会依次选择一棵有苹果的树（如果所有树上都没有苹果就不选），然后把这棵树以及可以通过绳索去到的其他树上的苹果全部摘下来。如果一只猴子摘下来了 x 个苹果，那么猴群的团结度就会乘以 x 。猴群的初始团结度为 1 。如果一只猴子没有摘到苹果，那么他就会离开猴群，所以不会影响团结度。

猴王想知道猴群的期望团结度是多少。请你帮帮他。

设答案为 s ，显然 s×n! 是一个整数。所以你只需要告诉他 ans=(s×n!) mod 998244353 的值 。

输入格式

一个整数 n 。

输出格式

一个整数 ans 。

样例

样例 1 输入

2

输出

3

若第一棵树比第二棵树矮，则团结度为 2 。 若第一棵树比第二棵树高，则团结度为 1 。 答案为 $\frac{2+1}{2} \times 2 = 3$。

样例 2 输入

5
输出

543

样例 3 输入

100

输出

795600847

样例 4 输入

50000

输出

480358544

数据范围与提示

子任务 1（10 分）：n≤10。 子任务 2（10 分）：n≤100。 子任务 3（20 分）：n≤5000。 子任务 4（40 分）：n≤10^5。 子任务 5（10 分）：n≤2×10^5。 子任务 6（10 分）：n≤5×10^5。

对于 100% 的数据：1≤n≤5×10^5。