#6402. yww 与校门外的树

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yww

题目描述

二中的校门外有一排树,一共 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

样例输出 1

3

样例说明 1

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

样例输入 2

5

样例输出 2

543

样例输入 3

100

样例输出 3

795600847

样例输入 4

50000

样例输出 4

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