Colin 最近收到了来自 Eva 的一份礼物：一个神秘的递增随机数序列生成器！你只需要输入一个正整数 $n$，生成器就会返回给你一个递增序列！经过反复实验，Colin 弄清楚了该生成器的工作原理。

最初，生成器会创建一个新的空序列，并等概率地从 $\{1, 2, \cdots, n\}$ 中选择一个数 $k$。

然后，生成器会等概率地从 $\{1, 2, \cdots, n\}$ 中选择一个数 $x$ 作为序列的第一个元素。

接下来，生成器会重复以下过程：

• 如果序列中的最大元素大于或等于 $k$，生成器将立即停止运行，并返回当前已经生成的序列。
• 否则，设序列中的最大元素为 $y$，则生成器会等概率地从 $\{y + 1, y + 2, \cdots, n\}$ 中选择一个数 $x$，并将 $x$ 追加到序列末尾。

现在 Colin 想知道，对于给定的 $n$，生成器返回的序列的期望长度是多少？

输入格式

单个整数 $n$（$1 \le n \le 10^7$）。

输出格式

单个整数，表示期望长度对 $998244353$ 取模后的结果。

样例

输入格式 1

3

输出格式 1

55458021

说明

• 若 $k = 1$，期望长度为 $1$。
• 若 $k = 2$，期望长度为 $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$。
• 若 $k = 3$，期望长度为 $1 \times \frac{1}{3} + 2 \times (\frac{1}{3} + \frac{1}{3} \times \frac{1}{2}) + 3 \times \frac{1}{3} \times \frac{1}{2} = \frac{11}{6}$。

因此，答案为 $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$。

$18$ 对 $998244353$ 的乘法逆元是 $720954255$，因此输出结果为 $25 \times 720954255 \bmod 998244353 = 55458021$。