respect:atgt2023ff

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

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

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

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

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

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

厳密な問題文

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

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

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

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

制約

• $N$ は整数
• $1\leq N\leq 3000$

入力

N

出力

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

サンプル

2

4

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

1

0

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

8

872904659

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

2536

524186647