{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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"},{"iden":"partial score","content":"This problem has partial scoring:\n\n*   If you solve all datasets with $N \\leq 14$, you will earn $3$ points."},{"iden":"input","content":"The input is given from standard input in the following format:\n\n$N$ $T$ $X$"},{"iden":"sample input 1","content":"2 3 2"},{"iden":"sample output 1","content":"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}$."},{"iden":"sample input 2","content":"10 12345 678"},{"iden":"sample output 2","content":"530802129"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}