#1025. [BJWC2018] 最长上升子序列

[BJWC2018] 最长上升子序列

题目描述

现在有一个长度为 nn 的随机排列,求它的最长上升子序列长度的期望。

为了避免精度误差,你只需要输出答案模 998244353998244353 的余数。

输入格式

输入只包含一个正整数 nn。

输出格式

输出只包含一个非负整数,表示答案模 998244353998244353 的余数。

可以证明,答案一定为有理数,设其为 a/ba/b(a,ba, b 为互质的整数),你输出的整数为 xx,则你需要保证 0≤x<9982443530 \le x < 998244353 且 aa 与 bxb x 模 998244353998244353 同余。

样例

1
1
2
499122178
3
2

题目来源:洛谷 P4484