Это сложная версия задачи. В этой версии задачи более высокие ограничения на \(h\) и \(w\).
Дом у моря имеет высоту в \(h\) этажей, все этажи имеют одинаковую высоту. На той стороне дома, которая обращена к морю, на каждом этаже расположено \(w\) окон на равных расстояниях друг от друга. Таким образом, окна расположены в клетках прямоугольной сетки \(h \times w\).
В каждом окне можно либо зажечь свет, либо нет, кроме заданных \(k\) (не более \(2\)) окон. В данных \(k\) окнах зажечь свет нельзя — лампочки перегорели.
Кораблю в море с помощью конфигурации включённого-выключенного света в темноте можно передавать сигналы. Однако с корабля не видно положение окон с включённым светом относительно дома. Поэтому если одну конфигурацию можно перевести в другую параллельным переносом окон с включённым светом, такие конфигурации считаются одинаковыми. Обратите внимание, что допустим только параллельный перенос — повороты и отражения недопустимы. Кроме того, конфигурация вообще без включённого света не считается допустимым сигналом.
Найдите, сколько разных сигналов можно передать кораблю, и выведите это число по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — сколько разных сигналов можно передать кораблю, по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных можно передать четыре разных сигнала: включить свет в любом окне, включить свет в двух соседних окнах, включить свет в двух крайних окнах или же включить свет во всех трех окнах.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|