Dice Expectation

問題文

$1$ 以上 $N$ 以下の整数が一様ランダムに出るサイコロがあります。

$1$ から $N$ までの整数が $1$ 回以上ことがある状態にするまでに振る必要のある回数の期待値 $\text{mod} ~ 998244353$ で求めてください。

期待値 mod 998244353 とは

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $y / x$ で表したとき、 $x \not\equiv 0 ~ (\text{mod} ~ 998244353)$ となることが保証されます。

このとき、 $xz \equiv y ~ (\bmod 998244353)$ を満たすような $0$ 以上 $998244353$ 未満の整数 $z$ が一意に定まります。この $z$ を答えてください。

制約

• 入力はすべて整数
• $1 \le N \le 10^6$

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

入出力例

入力例 1

3

出力例 1

499122182

$1$ 以上 $3$ 以下の整数が出るサイコロの目をすべて出すためにかかる回数の期待値は $\frac{33}{6}$ です。

入力例 2

1000000

出力例 2

697618461