AT_abc333_f [ABC333F] Bomb Game 2

[problemUrl]: https://atcoder.jp/contests/abc333/tasks/abc333_f $ N $ 人の人が一列に並んでおり、人 $ i $ は先頭から $ i $ 番目に並んでいます。 以下の操作を、列に並んでいる人が $ 1 $ 人になるまで繰り返します。 - 先頭に並んでいる人を $ \frac{1}{2} $ の確率で列から取り除き、そうでない場合は列の末尾に移す。 人 $ i=1,2,\ldots,N $ それぞれについて、人 $ i $ が最後まで列に並んでいる $ 1 $ 人になる確率を $ \text{mod\ }998244353 $ で求めて下さい。(取り除くかどうかの選択はすべてランダムかつ独立です。) 確率 $ \text{mod\ }\ 998244353 $ の定義この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz\ \equiv\ y\ \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

N/A

N/A

### 制約 - $ 2\leq\ N\leq\ 3000 $ - 入力は全て整数 ### Sample Explanation 1 人 $ 1 $ が最後まで列に並んでいる $ 1 $ 人になる確率は $ \frac{1}{3} $ です。 人 $ 2 $ が最後まで列に並んでいる $ 1 $ 人になる確率は $ \frac{2}{3} $ です。