[BJWC2018] 最长上升子序列

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

1

输出样例 #1

1

输入样例 #2

2

输出样例 #2

499122178

输入样例 #3

3

输出样例 #3

2

说明

**【样例 \#2 说明】** 这是 $3/2$。 **【数据规模和约定】** 对于 $100 \%$ 的数据,$1 \le n \le 28$。 共有 25 组数据,对于第 $i$ 组数据($1 \le i \le 25$),$n = i + 3$。