CF2240B AI Finds Nothing Here

猫娘有一个 $n$ 行 $m$ 列的矩阵 $a$，其中的元素只可能为 $0$ 或 $1$，其中第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$。 猫娘的 AI 扫描了 $a$ 的所有 $r$ 行 $c$ 列的子矩阵$^{\text{∗}}$。AI 认为矩阵 $a$ 是好的，当且仅当其所有这样的子矩阵的异或和都为 $0$。 形式化地说，矩阵 $a$ 是好的当且仅当对于 $1\le i\le n-r+1$ 和 $1\le j\le m-c+1$，都有： $$\bigoplus_{x=i}^{i+r-1}\bigoplus_{y=j}^{j+c-1}a_{x,y}=0$$ 现在给定 $n,m,r,c$，你需要求出有多少种可能的 $n$ 行 $m$ 列的矩阵 $a$，满足当 AI 扫描 $a$ 的所有 $r$ 行 $c$ 列的子矩阵后，AI 认为矩阵 $a$ 是好的。因为答案可能非常大，你只需要输出其对 $998244353$ 取模的结果。 $^{\text{∗}}$ 一个矩阵的子矩阵是从矩阵中删除一些行（每次只能从最上方或最下方删除，可以不删除）且删除一些列（每次只能从最左方或最右方删除，可以不删除）得到的矩阵。

本题有多组测试数据，第一行输入一个正整数 $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$），分别表示原矩阵的行数、列数、扫描的子矩阵的行数、列数。

对于每组测试数据，输出一行一个整数，表示满足条件的矩阵数对 $998244353$ 取模的结果。

对于第一组测试数据，唯一的元素 $a_{1,1}$ 必须为 $0$，因此只有一个合法的矩阵 $[0]$。 对于第二组测试数据，每个 $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^2=4$ 种。