AI 在此一无所获AI (CI翻译)
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 有一个 $n$ 行 $m$ 列的矩阵 $a$，其中的元素均为整数 $0$ 或 $1$。行从 $1$ 到 $n$ 编号，列从 $1$ 到 $m$ 编号。第 $i$ 行第 $j$ 列的元素记为 $a_{i,j}$。AI (CI翻译)
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$.
Milkcat2009 的 AI 会扫描 $a$ 中所有由 $r$ 行 $c$ 列组成的子矩阵$^{\text{∗}}$。如果每个这样的子矩阵中元素的按位异或和都等于 $0$，AI 就认为矩阵是干净的。AI (CI翻译)
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 $$
形式化地说，当且仅当对于所有 $1 \le i \le n - r + 1$ 和 $1 \le j \le m - c + 1$，满足以下条件时，矩阵 $a$ 是有效的： $$ \bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0 $$AI (CI翻译)
where $\oplus$ denotes summation with the bitwise XOR operation.
其中，$\oplus$ 表示按位异或运算。AI (CI翻译)
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$.
给定多组整数 $n, m, r, c$，请你计算满足扫描区域尺寸为 $r \times c$ 时，所有 $n$ 行 $m$ 列的干净矩阵的数量。由于答案可能很大，请对 $998\,244\,353$ 取模。AI (CI翻译)
$^{\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.
$^{\text{∗}}$矩阵的子矩阵可以通过从原矩阵的开头和/或末尾删除若干行和/或列得到。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个输入包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。AI (CI翻译)
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.
每个测试用例占一行，包含四个整数 $n, m, r, c$（$1 \le r \le n \le 10^9$，$1 \le c \le m \le 10^9$），分别表示矩阵的尺寸和扫描区域的尺寸。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, output a single integer representing the answer modulo $998\,244\,353$.
对于每个测试用例，输出一个整数，表示答案对 $998\,244\,353$ 取模后的结果。AI (CI翻译)
Note
说明
AI (CI翻译)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]$.
对于第一个测试用例，唯一的元素 $a_{1,1}$ 必须满足 $a_{1,1} = 0$。因此只有一个有效矩阵：$[0]$。AI (CI翻译)
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.
对于第二个测试用例，条件要求每个 $1 \times 2$ 子矩阵的异或和都为 $0$。这意味着 $a_{i,j} \oplus a_{i,j+1} = 0$，因此对所有有效的 $i,j$，都有 $a_{i,j} = a_{i,j+1}$。所以每一行的元素都必须相等。每一行可以是 $[0, 0, 0]$ 或 $[1, 1, 1]$。矩阵有 $2$ 行，因此共有 $2^2 =4$ 个有效矩阵。AI (CI翻译)
样例
8
1 1 1 1
2 3 1 2
2 5 2 2
3 5 2 2
4 6 2 2
100 14 52 6
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1 1
1
4
64
128
512
543661425
121099884
1
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。