2274: 最长上升子序列

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：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。

来源/分类

提交提交记录统计讨论版露一手!