Colin は最近、Eva からプレゼントを受け取りました。それは不思議な昇順乱数列生成器です！正の整数 $n$ を入力するだけで、生成器は昇順の数列を返してくれます！何度も実験を重ねた結果、Colin は生成器の仕組みを突き止めました。
まず、生成器は空の数列を新しく作成し、$\{1, 2, \dots, n\}$ から等確率で数 $k$ を $1$ つ選びます。
次に、生成器は数列の最初の要素として、$\{1, 2, \dots, n\}$ から等確率で数 $x$ を $1$ つ選びます。
その後、生成器は以下の処理を繰り返します：
- 数列内の最大要素が $k$ 以上である場合、生成器は直ちに停止し、すでに生成された現在の数列を返します。
- そうでなく、数列内の最大要素が $y$ である場合、生成器は $\{y + 1, y + 2, \dots, n\}$ から等確率で数 $x$ を $1$ つ選び、数列の末尾に $x$ を追加します。
Colin は今、与えられた $n$ に対して、生成器が返す数列の長さの期待値がいくらになるかを知りたいと考えています。
入力
整数 $n$ ($1 \le n \le 10^7$) が $1$ 行に与えられます。
出力
期待される長さを $998244353$ で割った余りを表す整数を $1$ 行に出力してください。
入出力例
入力 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$ となります。