東大理系数学1971第6問

2 secs 1024 MB
hayatroid's icon hayatroid

問題文

33 人で ’ジャンケン’ をして勝者をきめることにする。 たとえば,11 人が ’紙’ を出し,他の 22 人が ’石’ を出せば,ただ 11 回でちょうど 11 人の勝者がきまることになる。 33 人で ’ジャンケン’ をして,負けた人は次の回に参加しないことにして,ちょうど 11 人の勝者がきまるまで,’ジャンケン’ をくり返すことにする。 このとき,kk 回目に,はじめてちょうど 11 人の勝者がきまる確率 (mod998244353)\pmod{998244353} を求めよ。

注記

求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では,その値を互いに素な 22 つの整数 P,QP, Q を用いて PQ\frac{P}{Q} と表したとき,R×QP(mod998244353)R \times Q \equiv P \pmod{998244353} かつ 0R<9982443530 \leq R < 998244353 を満たす整数 RR がただ一つ存在することが証明できます。この RR を求めてください。

制約

  • 1k2×1051 \leq k \leq 2 \times 10^5

入力

入力はすべて整数である。

k

出力

計算結果を一行に出力せよ。

サンプル

入力1
1
出力1
332748118

11 回でちょうど 11 人の勝者がきまるのは,

  • 11 人が ’石’ を出し,残りの 22 人が ’ハサミ’ を出す
  • 11 人が ’ハサミ’ を出し,残りの 22 人が ’紙’ を出す
  • 11 人が ’紙’ を出し,残りの 22 人が ’石’ を出す

ときです。このようになる確率は 13\frac{1}{3} です。

入力2
114514
出力2
200889667

Submit


Go (1.21)