AT_fps_24_r ランダムウォーク

有一个简单无向图，共有 $2^N+1$ 个顶点和 $2^N$ 条边，顶点编号为 $1, 2, \dots, 2^N+1$。 第 $i$ 条边连接顶点 $i$ 和顶点 $i+1$。 你在顶点 $1$ 上放置一个棋子。然后，恰好重复 $T$ 次如下操作： - 设当前所在顶点为 $v$。从与 $v$ 相邻的顶点中等概率随机选择一个，并将棋子移动到该顶点。 在进行 $T$ 次操作后，计算棋子处于顶点 $X$ 的概率，并对 $998244353$ 取模输出。 什么是对 $998244353$ 取模的概率？可以证明概率总是一个有理数。在本题的约束下，假设这个概率为 $\tfrac{P}{Q}$，其中 $P,Q$ 互质，那么存在唯一的整数 $R$，使得 $R \times Q \equiv P \pmod{998244353}$，并且 $0 \leq R < 998244353$。你的任务就是计算这个 $R$。

输入从标准输入中获取，格式如下： > $N$ ~$T$ ~$X$

输出答案。

## 部分分数 本题有部分分计分： - 若你能解出所有 $N \leq 14$ 的测试点，可以获得 $3$ 分。 ## 样例解释 1 所有可能的移动及其概率如下： - 移动 $1 \to 2 \to 3 \to 2$，概率为 $\tfrac{1}{4}$。 - 移动 $1 \to 2 \to 1 \to 2$，概率为 $\tfrac{1}{2}$。 因此，答案为 $\tfrac{3}{4}$。 # 数据范围 - $1 \leq N \leq 20$ - $1 \leq T \leq 10^{18}$ - $1 \leq X \leq 2^N+1$ - 所有输入值均为整数。 由 ChatGPT 5 翻译