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$ を答えてください。

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

N

答えを出力せよ。

499122182

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

697618461