respect:atgt2023ff

問題文(ストーリーあり)

正の整数 NN が与えられます。

11 枚のピザがあります。このピザは半径 11 の円とみなすことができます。

このピザに対し、次の操作を NN 回行います。

  • [0,2π)[0,2 \pi ) からの一様な乱数として 22 つの実数を生成し、それを x,yx,y とする。ただし、x,yx,y は生成した順序で区別される。
  • (sinx,cosx)(\sin{x},\cos{x}) から (siny,cosy)(\sin{y},\cos{y}) へ、ピザの元々の円周上を通る弧で反時計回りに結ぶ。
  • その弧の端点 22 つとピザの中心をそれぞれ線分で結び、その 22 つの線分と弧で囲まれている部分のピザを食べる。

最終的にピザを全て食べきることができる確率に (2N)!(2N)! をかけた値は整数になることが示せます。これを 998244353998244353 で割った余りを求めてください。ただし、乱数は全て独立であるものとします。

厳密な問題文

正の整数 NN が与えられます。

次のような操作を行います。

  • まず、集合 SS を持つ。これは最初空である。
  • 次の操作を NN 回行う。
    • [0,2π)[0,2 \pi ) からの一様な乱数として 22 つの実数を生成し、それを x,yx,y とする。ただし、x,yx,y は生成した順序で区別される。
    • x>yx>y ならば、yy2π2\pi を加算する。
    • SSS{f(θ)xθy}S\cup{\lbrace f(\theta) | x\leq \theta \leq y \rbrace} で置き換える。ただし、f(θ)f(\theta) は次のように定義される。
      • θ<2π\theta <2\pi ならば、f(θ)=θf(\theta)=\theta
      • 2πθ2\pi \leq \theta ならば、f(θ)=θ2πf(\theta)=\theta - 2\pi

操作が終了した時点で S={θ0θ<2π}S= \lbrace \theta |0\leq \theta < 2\pi \rbrace となっている確率に (2N)!(2N)! をかけた値は整数になることが示せます。これを 998244353998244353 で割った余りを求めてください。ただし、乱数は全て独立であるものとします。

制約

  • NN は整数
  • 1N30001\leq N\leq 3000

入力

N

出力

操作が条件を満たす確率に (2N)!(2N)! をかけた値を 998244353998244353 で割った余りを出力してください。

サンプル

入力1
2
出力1
4

最初の操作によってピザが全体を 11 として pp だけ食べられた時、次の 11 回でピザを全て食べきる確率は p22\frac{p^2}{2} となります。 最初の操作が終了した時点での pp[0,1)[0,1) の一様な乱数と等しくなるため、問題の確率は 01p22dp=16\int_0^1 \frac{p^2}{2} dp =\frac{1}{6} となります。これに (2N)!=24(2N)!=24 をかけた 44 を出力してください。

入力2
1
出力2
0

一度の操作でピザを全て食べきる確率は 00 です。

入力3
8
出力3
872904659

確率は 244583167259459200\frac{244583167}{259459200} であり、これに 16!16! をかけた 1972318658688019723186586880998244353998244353 で割った余りである 872904659872904659 を出力してください。

入力4
2536
出力4
524186647

Submit


Go (1.21)