题目描述

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

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

输入格式

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

输出格式

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

可以证明，答案一定为有理数，设其为 $a/b$（$a, b$ 为互质的整数），你输出的整数为 $x$，则你需要保证 $0 \le x < 998244353$ 且 $a$ 与 $b x$ 模 $998244353$ 同余。

1

1

2

499122178

3

2

提示

【样例 #2 说明】

这是 $3/2$。

【数据规模和约定】

对于 $100 \%$ 的数据，$1 \le n \le 28$。

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