4900: [BJWC2018] 最长上升子序列

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

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

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



Input

输入只包含一个正整数 

Output

输出只包含一个非负整数,表示答案模 998244353 的余数。

可以证明,答案一定为有理数,设其为 /, 为互质的整数),你输出的整数为 ,则你需要保证 0<998244353 且  与  模 998244353 同余。

Sample Input Copy

2

Sample Output Copy

499122178

HINT

【样例 #2 说明】

这是 3/2

【数据规模和约定】

对于 100% 的数据,128

共有 25 组数据,对于第  组数据(125),=+3