小 i 最近了解到了一种用于生成"迷宫"的算法。它的具体流程如下：

首先准备一个大小为 $$$2^n \times 2^n$$$ 的正方形网格（$$$n$$$ 为正整数）。第 $$$i$$$ 行的第 $$$j$$$ 个格点的坐标记为 $$$(i, j)$$$（$$$0 \leq i,j \lt 2^n$$$）。

然后每个格点按照其 Hilbert 序依次编号为 $$$0$$$ 到 $$$4^n - 1$$$。

坐标 $$$(x, y)$$$ 的 Hilbert 序 $$$H(n, x, y)$$$ 递归定义如下：

$$$$$$ H(n, x, y) = \left \{ \begin{aligned} & 0 && && && && \text{ if } n = 0 \\ & H(n - 1 , && y , && x && ) && \text{ if } n \geq 1 \text{ and } 0 \leq x,y \lt 2^{n-1} \\ & H(n - 1 , && x , && y - 2^{n-1} && ) + 4^{n-1} && \text{ if } n \geq 1 \text{ and } 0 \leq x \lt 2^{n-1} \text{ and } 2^{n-1} \leq y \lt 2^n \\ & H(n - 1 , && x - 2^{n-1} , && y - 2^{n-1} && ) + 2 \cdot 4^{n-1} && \text{ if } n \geq 1 \text{ and } 2^{n-1} \leq x,y \lt 2^n \\ & H(n - 1 , && 2^{n-1} - y - 1 , && 2^n - x - 1 && ) + 3 \cdot 4^{n-1} && \text{ if } n \geq 1 \text{ and } 2^{n-1} \leq x \lt 2^n \text{ and } 0 \leq y \lt 2^{n-1} \end{aligned} \right. $$$$$$

以 $$$n = 3$$$ 的正方形网格为例，其中格点的 Hilbert 序如下图所示。

（不难发现这其实就是格点被二维希尔伯特曲线贯穿的顺序）

我们定义坐标 $$$(0, 0)$$$ 的格点为起点，坐标 $$$(2^n - 1, 0)$$$ 的格点为终点。

之后，我们在网格上进行连边操作。

具体的，对于除起点外的每个格点 $$$(x, y)$$$，我们将依次执行以下操作：

• 找到所有与 $$$(x, y)$$$ 相邻且 Hilbert 序小于 $$$H(n, x, y)$$$ 的格点，构成集合 $$$S$$$。
• 从 $$$S$$$ 中等概率随机选择一个格点 $$$(x', y')$$$，并在 $$$(x, y)$$$ 和 $$$(x', y')$$$ 之间连一条无向边。

这里所说的相邻定义为：如果两个格点 $$$(x_1, y_1)$$$ 与 $$$(x_2, y_2)$$$ 满足 $$$\left | x_1 - x_2 \right | + \left | y_1 - y_2 \right | = 1$$$，则我们称它们是相邻的。其中 $$$\left | x \right |$$$ 表示 $$$x$$$ 的绝对值。

以下是一种可能的连边结果（两个相邻的格点之间没有实线分隔，当且仅当它们之间有连边）。

我们定义起点到终点的距离，为两者之间的最短路径所经过的格点数（包括起点和终点）。

小 i 想要知道，在连边操作结束后，起点到终点的距离的期望是多少？请你计算这个期望对 $$$998 \, 244 \, 353$$$ 取模的结果。

具体的，可以证明，答案可以被表示成一个最简分数 $$$\frac{p}{q}$$$（$$$p$$$ 和 $$$q$$$ 互质且 $$$q$$$ 不被 $$$998 \, 244 \, 353$$$ 整除）。

你需要输出一个整数 $$$x$$$，满足 $$$0 \leq x \lt 998 \, 244 \, 353$$$ 且 $$$x \cdot q \equiv p \pmod{998 \, 244 \, 353}$$$。

可以证明，在连边操作结束后，起点和终点一定连通。