对于两个数组 $$$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$$$ 取模。
示例
输入复制
62 2 2 22 3 4 55 7 4 31337 42 1337 424 2 13 37536870902 536370902 536390912 466128231
输出复制
57 864 50360 439988899 112000 732195491