E. XOR Matrix
bitmasks; combinatorics; dp; implementation; math
For two arrays \(a = [a_1, a_2, \dots, a_n]\) and \(b = [b_1, b_2, \dots, b_m]\), we define the XOR matrix \(X\) of size \(n \times m\), where for each pair \((i,j)\) (\(1 \le i \le n\); \(1 \le j \le m\)) it holds that \(X_{i,j} = a_i \oplus b_j\). The symbol \(\oplus\) denotes the bitwise XOR operation.You are given four integers \(n, m, A, B\). Count the number of such pairs of arrays \((a, b)\) such that: \(a\) consists of \(n\) integers, each of which is from \(0\) to \(A\); \(b\) consists of \(m\) integers, each of which is from \(0\) to \(B\); in the XOR matrix formed from these arrays, there are no more than two distinct values.
The first line contains one integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.Each test case consists of one line containing four integers \(n, m, A, B\) (\(2 \le n, m, A, B \le 2^{29} - 1\)).
For each test case, output one integer — the number of pairs of arrays \((a, b)\) that satisfy all three conditions. Since this number can be very large, output it modulo \(998244353\).