问题2297--最长上升子序列

2297: 最长上升子序列

时间限制: 1 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

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

Input


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

对于 100%的数据,1≤n≤28。
共有 25组数据  ,对于第 i组数据 (1≤i≤25), n=i+3。


Output

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

Sample Input

2

Sample Output

499122178
【样例说明】
这是3/2。

来源/分类


[提交] [状态]