H2. Оконные сигналы (сложная версия)
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии задачи более высокие ограничения на $$$h$$$ и $$$w$$$.

Дом у моря имеет высоту в $$$h$$$ этажей, все этажи имеют одинаковую высоту. На той стороне дома, которая обращена к морю, на каждом этаже расположено $$$w$$$ окон на равных расстояниях друг от друга. Таким образом, окна расположены в клетках прямоугольной сетки $$$h \times w$$$.

В каждом окне можно либо зажечь свет, либо нет, кроме заданных $$$k$$$ (не более $$$2$$$) окон. В данных $$$k$$$ окнах зажечь свет нельзя — лампочки перегорели.

Кораблю в море с помощью конфигурации включённого-выключенного света в темноте можно передавать сигналы. Однако с корабля не видно положение окон с включённым светом относительно дома. Поэтому если одну конфигурацию можно перевести в другую параллельным переносом окон с включённым светом, такие конфигурации считаются одинаковыми. Обратите внимание, что допустим только параллельный перенос — повороты и отражения недопустимы. Кроме того, конфигурация вообще без включённого света не считается допустимым сигналом.

Найдите, сколько разных сигналов можно передать кораблю, и выведите это число по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$h$$$, $$$w$$$ и $$$k$$$ ($$$1 \le h, w \le 200$$$; $$$0 \le k \le \min(h \cdot w, 2)$$$) — высоту дома, число окон на каждом этаже дома и число окон, в которых свет зажечь нельзя.

Если $$$k > 0$$$, то каждая из следующих $$$k$$$ строк содержит два целых числа $$$r_i$$$ и $$$c_i$$$ ($$$1 \le r_i \le h$$$; $$$1 \le c_i \le w$$$) — номер этажа и номер окна на этаже, в котором нельзя включить свет. Этажи пронумерованы от $$$1$$$ до $$$h$$$ снизу вверх, а окна на каждом этаже — от $$$1$$$ до $$$w$$$ слева направо. Если $$$k = 2$$$, то либо $$$r_1 \ne r_2$$$, либо $$$c_1 \ne c_2$$$.

Гарантируется, что сумма $$$h \cdot w$$$ по всем наборам входных данных не превосходит $$$40\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сколько разных сигналов можно передать кораблю, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
10
1 3 0
2 2 0
3 2 0
4 5 0
12 7 0
1 1 1
1 1
1 3 1
1 2
3 4 1
3 4
2 3 2
1 1
2 1
4 5 2
2 3
4 2
Выходные данные
4
10
44
954368
34903934
0
2
1696
10
253144
Примечание

В первом наборе входных данных можно передать четыре разных сигнала: включить свет в любом окне, включить свет в двух соседних окнах, включить свет в двух крайних окнах или же включить свет во всех трех окнах.