Milkcat2009 有一个矩阵 $$$a$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,由整数 $$$0$$$ 和 $$$1$$$ 组成。行的编号从 $$$1$$$ 到 $$$n$$$,列的编号从 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 行和 $$$j$$$ 列中的元素表示为 $$$a_{i,j}$$$。
Milkcat2009 的 AI 扫描由 $$$r$$$ 行和 $$$c$$$ 列组成的 $$$a$$$ 的每个子矩阵$$$^{\text{∗}}$$$。 AI 考虑矩阵 干净 如果每个此类子矩阵中元素的按位异或和等于 $$$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$$
其中 $$$\oplus$$$ 表示按位异或运算求和。
你的任务是,给定各种整数集 $$$n, m, r, c$$$,计算 干净 相对于扫描维度 $$$r$$$ 和 $$$c$$$ 的 $$$n$$$ 行和 $$$m$$$ 列矩阵。由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模进行计算。
$$$^{\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$$$) 组成,分别代表矩阵的维度和扫描区域的维度。
输出
对于每个测试用例,输出一个表示答案模 $$$998\,244\,353$$$ 的整数。
示例
输入复制
81 1 1 12 3 1 22 5 2 23 5 2 24 6 2 2100 14 52 61000000000 1000000000 1000000000 10000000001000000000 1000000000 1 1
输出复制
14641285125436614251210998841
注意
对于第一个测试用例。唯一的元素 $$$a_{1,1}$$$ 必须满足 $$$a_{1,1} = 0$$$。由于 $$$a_{1,1}$$$ 必须是 $$$0$$$,因此只有 $$$1$$$ 有效矩阵:$$$[0]$$$。
对于第二个测试用例。条件要求每个 $$$1 \times 2$$$ 子矩阵的 XOR 和为 $$$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$$$ 有效矩阵。