AT_fps_24_r ランダムウォーク

頂点に $ 1, 2, \dots, 2^N+1 $ の番号がついた $ 2^N+1 $ 頂点 $ 2^N $ 辺の単純無向グラフがあります。 $ i $ 番目の辺は頂点 $ i $ と頂点 $ i+1 $ を結んでいます。 あなたは頂点 $ 1 $ に駒を置きます。その後、以下の操作をちょうど $ T $ 回繰り返します。 - 現在駒がある頂点を $ v $ とする。 $ v $ に隣接する頂点の中から $ 1 $ 個の頂点を一様ランダムに選び、選んだ頂点に駒を移動させる。 $ T $ 回の操作を終了した時点で頂点 $ X $ に駒がある確率を $ \text{mod }998244353 $ で求めてください。 確率 $ \text{mod }998244353 $ とは 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $ , $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、 $ R \times Q \equiv P\pmod{998244353} $ かつ $ 0 \leq R \lt 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ X $

答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N \leq 14 $ を満たすデータセットに正解した場合、 $ 3 $ 点が与えられる。 ### Sample Explanation 1 条件を満たす移動およびその確率を列挙すると、 - 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 2 $ と移動する確率が $ \frac{1}{4} $ 、 - 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ と移動する確率が $ \frac{1}{2} $ となります。よって答えは $ \frac{3}{4} $ です。 ### Constraints - $ 1 \leq N \leq 20 $ - $ 1 \leq T \leq 10^{18} $ - $ 1 \leq X \leq 2^N+1 $ - 入力される値は全て整数