[BJWC2018]最长上升子序列

题目描述

现在有一个长度为n的随机排列,求它的最长上升子序列长度的期望。 为了避免精度误差,你只需要输出答案模998244353的余数。

输入输出格式

输入格式


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

输出格式


输出只包含一个非负整数,表示答案模998244353的余数。 可以证明,答案一定为有理数,设其为a/b(a、b为互质的整数),你输出的整数为x,则你需要保证0≤x<998244353且a与bx模998244353同余。

输入输出样例

输入样例 #1

1

输出样例 #1

1

输入样例 #2

2

输出样例 #2

499122178

输入样例 #3

3

输出样例 #3

2

说明

**【样例#2说明】** 这是3/2。 **【数据规模和约定】** 对于 100% 的数据 ,1≤n≤28。 共有 25 组数据 ,对于第i组数据 (1≤i≤25), n=i+3。