M - Reversal Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

高橋くんと青木くんが、N 本先取でゲームの試合をします。高橋くんと青木くんの実力は全く同じであり、すべてのゲームは前後のゲームの結果等に左右されず、常に独立に高橋くんと青木くんが \frac{1}{2} ずつの確率で勝ちます。引き分けはありません。

(高橋くんの勝ち数, 青木くんの勝ち数) が (2,1) から (2,3) に動くことのように、2 ゲームが経過する間に 2 人の勝ち数の大小が入れ替わることを「逆転」と呼ぶことにします。

2 人の試合の決着がつくまでに起こる「逆転」の回数の期待値を\mod 998244353 で求めてください（注記参照）。

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 2 \leq N \leq 10^7
  • 入力はすべて整数

入力

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

N

出力

期待値を\mod 998244353 で出力せよ。

入力例 1

2

出力例 1

748683265

以下の 2 パターンのみ「逆転」が 1 回起きます。それ以外のパターンでは「逆転」は一度も起きません。

  • 高橋くんが勝つ → 青木くんが勝つ → 青木くんが勝つ
  • 青木くんが勝つ → 高橋くんが勝つ → 高橋くんが勝つ

これらのパターンは \frac{1}{8} ずつの確率で発生するため、期待値は \frac{1}{4} となります。

748683265 \times 4 \equiv 1\pmod{998244353} より、748683265 を出力してください。

入力例 2

4

出力例 2

405536769

入力例 3

621998

出力例 3

76706976

Score : 6 points

Problem Statement

Takahashi and Aoki will play a match where the first to win N games wins. The two players are equally skilled, and each of them wins a game with probability \frac{1}{2}, independently of the outcomes of the other games. There are no draws.

A reversal is said to occur when the player with more wins changes in two games, as in going from 2-1 to 2-3 (now Aoki is in the lead).

Find the expected value of the number of reversals until one player wins the match, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there uniquely exists one integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

  • 2 \leq N \leq 10^7
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the expected value modulo 998244353.

Sample Input 1

2

Sample Output 1

748683265

There is one reversal only in the two scenarios below, and no reversal in the other scenarios.

  • Takahashi wins, then Aoki wins, then Aoki wins.
  • Aoki wins, then Takahashi wins, then Takahashi wins.

Each of them occurs with probability \frac{1}{8}, so the sought expected value is \frac{1}{4}.

We have 748683265 \times 4 \equiv 1\pmod{998244353}, so print 748683265.

Sample Input 2

4

Sample Output 2

405536769

Sample Input 3

621998

Sample Output 3

76706976