AT_fps_24_r ランダムウォーク

There is a simple undirected graph with $ 2^N+1 $ vertices and $ 2^N $ edges, where the vertices are numbered $ 1, 2, \dots, 2^N+1 $ . The $ i $ -th edge connects vertex $ i $ and vertex $ i+1 $ . You place a piece on vertex $ 1 $ . Then you repeat the following operation exactly $ T $ times: - Let the current vertex be $ v $ . Choose one adjacent vertex of $ v $ uniformly at random, and move the piece to that vertex. After $ T $ operations, compute the probability that the piece is on vertex $ X $ , modulo $ 998244353 $ . What does probability modulo $ 998244353 $ mean? It can be proven that the probability is always a rational number. Under the constraints of this problem, if the probability is written as $ \tfrac{P}{Q} $ with coprime integers $ P $ and $ Q $ , then there exists a unique integer $ R $ such that $ R \times Q \equiv P \pmod{998244353} $ and $ 0 \leq R < 998244353 $ . You are asked to compute this $ R $ .

The input is given from standard input in the following format: > $ N $ $ T $ $ X $

Print the answer.

### Partial Score This problem has partial scoring: - If you solve all datasets with $ N \leq 14 $ , you will earn $ 3 $ points. ### Sample Explanation 1 The possible moves and their probabilities are: - Move $ 1 \to 2 \to 3 \to 2 $ with probability $ \tfrac{1}{4} $ . - Move $ 1 \to 2 \to 1 \to 2 $ with probability $ \tfrac{1}{2} $ . Thus, the answer is $ \tfrac{3}{4} $ . ### Constraints - $ 1 \leq N \leq 20 $ - $ 1 \leq T \leq 10^{18} $ - $ 1 \leq X \leq 2^N+1 $ - All input values are integers