#5161. 最长上升子序列

内存限制:512 MiB 时间限制:10 Sec

题目描述

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

输入格式

输入只包含一个正整数n。N<=28

输出格式

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

样例

样例输入


			
2

样例输出


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

数据范围与提示