B. ИИ ничего здесь не найдёт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Milkcat2009 есть матрица $$$a$$$ из $$$n$$$ строк и $$$m$$$ столбцов, состоящая из целых чисел $$$0$$$ и $$$1$$$. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы — от $$$1$$$ до $$$m$$$. Элемент в $$$i$$$-й строке и $$$j$$$-м столбце обозначается как $$$a_{i,j}$$$.

ИИ Milkcat2009 сканирует каждую подматрицу$$$^{\text{∗}}$$$ матрицы $$$a$$$, состоящую из $$$r$$$ строк и $$$c$$$ столбцов. ИИ считает матрицу чистой, если побитовый XOR элементов в каждой такой подматрице равен $$$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$$$ обозначает суммирование с операцией побитового XOR.

Ваша задача — для нескольких наборов целых чисел $$$n, m, r, c$$$ подсчитать количество чистых матриц из $$$n$$$ строк и $$$m$$$ столбцов при заданных размерах области сканирования $$$r$$$ и $$$c$$$. Так как ответ может быть очень большим, вычислите его по модулю $$$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$$$.

Пример
Входные данные
8
1 1 1 1
2 3 1 2
2 5 2 2
3 5 2 2
4 6 2 2
100 14 52 6
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1 1
Выходные данные
1
4
64
128
512
543661425
121099884
1
Примечание

Для первого набора входных данных единственный элемент $$$a_{1,1}$$$ должен удовлетворять условию $$$a_{1,1} = 0$$$. Так как $$$a_{1,1}$$$ обязан быть равен $$$0$$$, существует только $$$1$$$ допустимая матрица: $$$[0]$$$.

Для второго набора входных данных условие требует, чтобы XOR-сумма каждой подматрицы $$$1 \times 2$$$ была равна $$$0$$$. Это означает $$$a_{i,j} \oplus a_{i,j+1} = 0$$$, то есть $$$a_{i,j} = a_{i,j+1}$$$ для всех допустимых $$$i,j$$$. В каждой строке все элементы должны быть равны. Таким образом, каждая строка может быть либо $$$[0, 0, 0]$$$, либо $$$[1, 1, 1]$$$. При $$$2$$$ строках существует $$$2^2 =4$$$ допустимых матрицы.