C - Catastrophic Roulette Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 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 は 1 \le N \le 10^6 を満たす整数

入力

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

N

出力

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

入力例 1

1

出力例 1

0 0

この入力では N=1 です。
先攻がルーレットを回すと必ず 1 が出て、直ちにゲームが終了します。
よって、支払う罰金の期待値は先攻後攻ともに 0 です。

入力例 2

2

出力例 2

332748118 665496236

この入力では N=2 です。ゲームの進行の一例は以下の通りです。

  • 先攻がルーレットを回し、 2 が出た。この時、何も起こらない。
  • 後攻がルーレットを回し、 2 が出た。この時、後攻は罰金 1 円を支払う。
  • 先攻がルーレットを回し、 2 が出た。この時、先攻は罰金 1 円を支払う。
  • 後攻がルーレットを回し、 1 が出た。この時、何も起こらない。
  • この時点で 1,2 が少なくとも 1 度出たので、直ちにゲームが終了する。
  • このようにゲームが進行した場合、先攻が支払う罰金は 1 円、後攻が支払う罰金も 1 円となります。

先攻が支払う罰金の期待値は \frac{1}{3} 円、後攻が支払う罰金の期待値は \frac{2}{3} 円であることが示せます。

入力例 3

3

出力例 3

174692763 324429416

Points: 500 points

Problem Statement

There is a roulette that produces an integer from 1,2,\dots,N with equal probability.
Two players use it to play the following game:

  • The players take turns spinning the roulette.
    • If the produced integer has not appeared before, nothing happens.
    • Otherwise, the player who spun the roulette pays a fine of 1 yen.
  • The game immediately ends when all of the N integers have appeared at least once.

For each of the first and second players, find the expected value of the amount of the fine paid before the game ends, modulo 998244353.

On expected values modulo 998244353

It can be proved that the expected values sought in this problem are always rational numbers. Furthermore, under the constraints of this problem, when the expected values are expressed as irreducible fractions \frac{y}{x}, it is guaranteed that x is not divisible by 998244353.

Now, there is a unique integer z between 0 and 998244352, inclusive, such that xz \equiv y \pmod{998244353}. Provide this z as the answer.

Constraints

  • N is an integer such that 1 \le N \le 10^6.

Input

The input is given from Standard Input in the following format:

N

Output

Print two integers as the answer.
The first is the expected value of the amount of the fine paid by the first player, and the second is the expected value of the amount of the fine paid by the second player, represented as integers modulo 998244353.

Sample Input 1

1

Sample Output 1

0 0

In this input, N=1.
When the first player spins the roulette, it always produces 1, ending the game immediately.
Thus, the expected values of the amounts of the fines paid by the first and second players are both 0.

Sample Input 2

2

Sample Output 2

332748118 665496236

In this input, N=2. Here is a possible progression of the game:

  • The first player spins the roulette, and it produces 2. Nothing happens.
  • The second player spins the roulette, and it produces 2. The second player pays a fine of 1 yen.
  • The first player spins the roulette, and it produces 2. The first player pays a fine of 1 yen.
  • The second player spins the roulette, and it produces 1. Nothing happens.
  • At this point, both 1 and 2 have appeared at least once, so the game immediately ends.
  • In this progression, the amount of the fine paid by the first player is 1 yen, and the amount of the fine paid by the second player is also 1 yen.

It can be shown that the expected value of the amount of the fine paid by the first player is \frac{1}{3} yen, and the expected value of the amount of the fine paid by the second player is \frac{2}{3} yen.

Sample Input 3

3

Sample Output 3

174692763 324429416