AT_arc174_c [ARC174C] Catastrophic Roulette

[problemUrl]: https://atcoder.jp/contests/arc174/tasks/arc174_c 整数 $ 1,2,\dots,N $ が均等な確率で出るルーレットがあります。 これを使って $ 2 $ 人で以下のゲームを行います。 - 先攻と後攻が交互にルーレットを回す。 - 出た整数が今までに出ていないものであった場合、何も起こらない。 - そうでない場合、ルーレットを回したプレイヤーが罰金 $ 1 $ 円を支払う。 - $ N $ 個の整数全てが少なくとも $ 1 $ 度出たとき、直ちにゲームが終了する。 先攻後攻それぞれについて、ゲームが終了するまでに支払う罰金の期待値を $ \text{mod}\ 998244353 $ で求めてください。 期待値 $ \text{mod\ }\ 998244353 $ の定義この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz\ \equiv\ y\ \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

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

答えとして $ 2 $ つの整数を出力せよ。 そのうち $ 1 $ つ目は先攻が支払う罰金の期待値、 $ 2 $ つ目は後攻が支払う罰金の期待値をそれぞれ $ \text{mod}\ 998244353 $ で表現した整数である。

### 制約 - $ N $ は $ 1\ \le\ N\ \le\ 10^6 $ を満たす整数 ### Sample Explanation 1 この入力では $ N=1 $ です。 先攻がルーレットを回すと必ず $ 1 $ が出て、直ちにゲームが終了します。 よって、支払う罰金の期待値は先攻後攻ともに $ 0 $ です。 ### Sample Explanation 2 この入力では $ N=2 $ です。ゲームの進行の一例は以下の通りです。 - 先攻がルーレットを回し、 $ 2 $ が出た。この時、何も起こらない。 - 後攻がルーレットを回し、 $ 2 $ が出た。この時、後攻は罰金 $ 1 $ 円を支払う。 - 先攻がルーレットを回し、 $ 2 $ が出た。この時、先攻は罰金 $ 1 $ 円を支払う。 - 後攻がルーレットを回し、 $ 1 $ が出た。この時、何も起こらない。 - この時点で $ 1,2 $ が少なくとも $ 1 $ 度出たので、直ちにゲームが終了する。 - このようにゲームが進行した場合、先攻が支払う罰金は $ 1 $ 円、後攻が支払う罰金も $ 1 $ 円となります。 先攻が支払う罰金の期待値は $ \frac{1}{3} $ 円、後攻が支払う罰金の期待値は $ \frac{2}{3} $ 円であることが示せます。