题目描述

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

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

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

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

设答案为 $s$ ，显然 $s\times n!$ 是一个整数。所以你只需要告诉他 $\mathit{ans}=(s\times n!)\bmod 998244353$ 的值 。

输入格式

一个整数 $n$ 。

输出格式

一个整数 $\mathit{ans}$ 。

样例 1

2

3

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

5

543

100

795600847

50000

480358544

数据范围与提示

子任务 $1$（$10$ 分）：$n\leq 10$。
子任务 $2$（$10$ 分）：$n\leq 100$。
子任务 $3$（$20$ 分）：$n\leq 5000$。
子任务 $4$（$40$ 分）：$n\leq 10^5$。
子任务 $5$（$10$ 分）：$n\leq 2\times 10^5$。
子任务 $6$（$10$ 分）：$n\leq 5\times 10^5$。
对于 $100\%$ 的数据：$1\leq n\leq 5\times 10^5$。

题目来源：全是水题的 GDOI 模拟赛 by yww