3014. [BJWC 2018]最长上升子序列

【题目描述】

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