{"problem":{"name":"Random Walk","description":{"content":"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 pie","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"fps_24_r"},"statements":[{"statement_type":"Markdown","content":"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$.  \nThe $i$\\-th edge connects vertex $i$ and vertex $i+1$.\nYou place a piece on vertex $1$. Then you repeat the following operation exactly $T$ times:\n\n*   Let the current vertex be $v$. Choose one adjacent vertex of $v$ uniformly at random, and move the piece to that vertex.\n\nAfter $T$ operations, compute the probability that the piece is on vertex $X$, modulo $998244353$.\nWhat 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$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 20$\n*   $1 \\leq T \\leq 10^{18}$\n*   $1 \\leq X \\leq 2^N+1$\n*   All input values are integers\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$N$ $T$ $X$\n\n## Partial Score\n\nThis problem has partial scoring:\n\n*   If you solve all datasets with $N \\leq 14$, you will earn $3$ points.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_r","tags":[],"sample_group":[["2 3 2","249561089\n\nThe possible moves and their probabilities are:\n\n*   Move $1 \\to 2 \\to 3 \\to 2$ with probability $\\tfrac{1}{4}$.\n*   Move $1 \\to 2 \\to 1 \\to 2$ with probability $\\tfrac{1}{2}$.\n\nThus, the answer is $\\tfrac{3}{4}$."],["10 12345 678","530802129"]],"created_at":"2026-03-03 11:01:14"}}