← 返回题目列表

Codeforces · 2075/E

E. 异或矩阵

中文机器翻译题面 查看原题

对于两个数组 $$$a = [a_1, a_2, \dots, a_n]$$$ 和 $$$b = [b_1, b_2, \dots, b_m]$$$,我们定义大小为 $$$n \times m$$$ 的 XOR 矩阵 $$$X$$$,其中对于每对 $$$(i,j)$$$ ($$$1 \le i \le n$$$; $$$1 \le j \le m$$$) 它认为 $$$X_{i,j} = a_i \oplus b_j$$$。符号$$$\oplus$$$表示按位异或运算。

给你四个整数 $$$n, m, A, B$$$。计算此类数组 $$$(a, b)$$$ 的数量,使得:

  • $$$a$$$由$$$n$$$个整数组成,每个整数从$$$0$$$到$$$A$$$;
  • $$$b$$$由$$$m$$$个整数组成,每个整数从$$$0$$$到$$$B$$$;
  • 在由这些数组形成的XOR矩阵中,不超过两个不同的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含四个整数 $$$n, m, A, B$$$ ($$$2 \le n, m, A, B \le 2^{29} - 1$$$)。

输出

对于每个测试用例,输出一个整数 — 满足所有三个条件的数组 $$$(a, b)$$$ 的对数。由于这个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

示例

输入
复制

6
2 2 2 2
2 3 4 5
5 7 4 3
1337 42 1337 42
4 2 13 37
536870902 536370902 536390912 466128231

输出
复制

57
864
50360
439988899
112000
732195491