CF2240B.AI Finds Nothing Here

Milkcat2009 has a matrix $a$ with $n$ rows and $m$ columns consisting of integers $0$ and $1$. The rows are numbered from $1$ to $n$, and the columns are numbered from $1$ to $m$. The element in the $i$-th row and $j$-th column is denoted as $a_{i,j}$.

Milkcat2009's AI scans every single submatrix$^{\text{∗}}$ of $a$ consisting of $r$ rows and $c$ columns. The AI considers the matrix clean if the bitwise XOR sum of elements in each such submatrix is equal to $0$.

Formally, the matrix $a$ is valid if and only if for all $1 \le i \le n - r + 1$ and $1 \le j \le m - c + 1$: $$ \bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0 $$

where $\oplus$ denotes summation with the bitwise XOR operation.

Your task is, given various sets of integers $n, m, r, c$, to count the number of clean matrices of $n$ rows and $m$ columns with respect to scanning dimensions $r$ and $c$. Since the answer can be very large, calculate it modulo $998\,244\,353$.

$^{\text{∗}}$A submatrix of a matrix is obtained by removing some rows (from the beginning and/or end) and/or columns (from the beginning and/or end) from the original matrix.

Milkcat2009 有一个由 $0$ 和 $1$ 组成的 $n$ 行 $m$ 列矩阵 $a$。行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。第 $i$ 行第 $j$ 列的元素记为 $a_{i,j}$。

Milkcat2009 的人工智能会扫描矩阵 $a$ 的每一个大小为 $r$ 行 $c$ 列的子矩阵$^{\text{∗}}$。若每个这样的子矩阵中所有元素的按位异或（XOR）和等于 $0$，则该人工智能认为该矩阵是“洁净的”。

形式化地，矩阵 $a$ 是有效的当且仅当对所有满足 $1 \le i \le n - r + 1$ 和 $1 \le j \le m - c + 1$ 的 $i, j$，均有：

$$\bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0$$

其中 $\oplus$ 表示按位异或运算。

你的任务是：对于给定的多组整数 $n, m, r, c$，计算关于扫描尺寸 $r$ 和 $c$ 的 $n$ 行 $m$ 列洁净矩阵的个数。由于答案可能非常大，请对 $998\,244\,353$ 取模。

$^{\text{∗}}$ 矩阵的一个子矩阵是通过从原矩阵的开头和/或结尾删除若干行和/或列而得到的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case consists of a single line containing four integers $n, m, r, c$ ($1 \le r \le n \le 10^9$, $1 \le c \le m \le 10^9$), representing the dimensions of the matrix and the dimensions of the scanning area, respectively.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例由一行组成，包含四个整数 $n, m, r, c$（$1 \le r \le n \le 10^9$，$1 \le c \le m \le 10^9$），分别表示矩阵的维度和扫描区域的维度。

For each test case, output a single integer representing the answer modulo $998\,244\,353$.

对于每个测试用例，输出一个整数，表示答案对 $998\,244\,353$ 取模的结果。

For the first test case. The only element $a_{1,1}$ must satisfy $a_{1,1} = 0$. Since $a_{1,1}$ must be $0$, there is only $1$ valid matrix: $[0]$.

For the second test case.The condition requires the XOR sum of every $1 \times 2$ submatrix to be $0$. This implies $a_{i,j} \oplus a_{i,j+1} = 0$, so $a_{i,j} = a_{i,j+1}$ for all valid $i,j$. For each row, all elements must be equal. Thus, each row can be either $[0, 0, 0]$ or $[1, 1, 1]$. With $2$ rows, there are $2^2 =4$ valid matrices.

对于第一个测试用例：唯一元素 $a_{1,1}$ 必须满足 $a_{1,1} = 0$。由于 $a_{1,1}$ 必须为 $0$，因此仅存在 $1$ 个有效矩阵：$[0]$。

对于第二个测试用例：条件要求每个 $1 \times 2$ 子矩阵的异或和为 $0$。这意味着对所有合法的 $i,j$，均有 $a_{i,j} \oplus a_{i,j+1} = 0$，即 $a_{i,j} = a_{i,j+1}$。因此，每行中所有元素必须相等。于是，每行只能是 $[0, 0, 0]$ 或 $[1, 1, 1]$。由于共有 $2$ 行，故有效矩阵总数为 $2^2 = 4$。