3704: 武义寺(第七轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给， 小和 尚叫扶弱呱。老和尚说“从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。 老和尚叫扶弱给，小和尚叫扶弱呱 … …”
有一天，扶弱给在潜心研究排列。他在脑中随机一个排列的时候，脑海里冒出了 这样一个问题：
对于一个排列p = {1,2, . . . , n} ，记val(p)等于最小的i 满足i > ai ，如不存在则 val(p) = n + 1。
可是val(p)的期望值是多少呢？显然，扶弱给没学过编程，需要你来帮帮他。
本场比赛大样例 ：
https://uploadfiles.nowcoder.com/files/20211016/%E5%A4%A7%E6%A0%B7%E4%BE %8B.zip
输入
输入一个数n。
输出
输出val(p)的期望值，答案对998244353取模。
样例输入 复制
2样例输出 复制
499122179提示
【样例 1 说明】
对于排列p = [1,2] ，val(p) = 3；对于排列p = [2,1] ，val(p) = 2。因此期望值为 5/2。
【数据范围】
对于 30% 的数据， 1 ≤ n ≤ 5 ；
对于 50% 的数据， 1 ≤ n ≤ 20 ；
对于 80% 的数据， 1 ≤ n ≤ 10^5 ；
对于 100% 的数据， 1 ≤ n ≤ 10^6 。