Colin 最近收到了 Eva 送的禮物：一個神秘的遞增隨機數列產生器！你只需要輸入一個正整數 $n$，產生器就會回傳一個遞增數列給你！經過反覆實驗，Colin 摸清了產生器的運作方式。

最初，產生器會建立一個新的空數列，並從 $\{1, 2, \dots, n\}$ 中等機率選取一個數字 $k$。

接著，產生器會從 $\{1, 2, \dots, n\}$ 中等機率選取一個數字 $x$ 作為數列的第一個元素。

接下來，產生器會重複以下過程：

• 如果數列中的最大元素大於或等於 $k$，產生器將立即停止運行並回傳當前已生成的數列。
• 否則，若數列中的最大元素為 $y$，則產生器會從 $\{y + 1, y + 2, \dots, 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$。