E. XOR-матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для двух массивов $$$a = [a_1, a_2, \dots, a_n]$$$ и $$$b = [b_1, b_2, \dots, b_m]$$$ определим XOR-матрицу $$$X$$$ размера $$$n \times m$$$, где для каждой пары $$$(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