1472 - 最长上升子序列

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 512 MB

现在有一个长度为n的随机排列，求它的最长上升子序列长度的期望。

为了避免精度误差，你只需要输出答案模998244353的余数。

Input

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

对于 100%的数据，1≤n≤28。<br />

共有 25组数据，对于第 i组数据（1≤i≤25）， n=i+3。

<br />

Output

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

Sample Input

<span class="sampledata">2</span>

Sample Output

<span class="sampledata">499122178<br />

1472 - 最长上升子序列

Input

输入

输出

样例

输入

输出

来源