#512. 最长上升子序列

最长上升子序列

说明

现在有一个长度为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。

样例