Window Signals (easy version)
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 3200

This is the easy version of the problem. In this version, the constraints on $$$h$$$ and $$$w$$$ are lower.

A house at the sea has $$$h$$$ floors, all of the same height. The side of the house facing the sea has $$$w$$$ windows at equal distances from each other on every floor. Thus, the windows are positioned in cells of a rectangular grid of size $$$h \times w$$$.

In every window, the light can be turned either on or off, except for the given $$$k$$$ (at most $$$2$$$) windows. In these $$$k$$$ windows the light can not be turned on, because it is broken.

In the dark, we can send a signal to a ship at sea using a configuration of lights turned on and off. However, the ship can not see the position of the lights with respect to the house. Thus, if one configuration of windows with lights on can be transformed into another using parallel translation, these configurations are considered equal. Note that only parallel translation is allowed, but neither rotations nor flips are. Moreover, a configuration without any light at all is not considered valid.

Find how many different signals the ship can receive and print this number modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$h$$$, $$$w$$$, and $$$k$$$ ($$$1 \le h, w \le 40$$$; $$$0 \le k \le \min(h \cdot w, 2)$$$) — the height of the house, the number of windows on each floor, and the number of windows with broken lights.

If $$$k > 0$$$, each of the next $$$k$$$ lines contains two integers $$$r_i$$$ and $$$c_i$$$ ($$$1 \le r_i \le h$$$; $$$1 \le c_i \le w$$$) — the floor number and the window number with the broken light. The floors are numbered $$$1$$$ to $$$h$$$ from bottom to top, and the windows are numbered $$$1$$$ to $$$w$$$ from left to right. If $$$k = 2$$$, then either $$$r_1 \ne r_2$$$ or $$$c_1 \ne c_2$$$.

It is guaranteed that the sum of $$$h \cdot w$$$ over all test cases does not exceed $$$1600$$$.

Output format:
For each test case, print a single integer — the number of signals the ship can receive, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the ship can receive four different signals: all lights on; lights on in two neighboring windows; lights on in the leftmost and the rightmost windows; or light on in any single window.

Example input:
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

Example output:
4
10
44
954368
34903934
0
2
1696
10
253144

Editorial:
Let's iterate over the dimensions of the bounding box of the image of windows with lights on, $$$h' \times w'$$$ ($$$1 \le h' \le h; 1 \le w' \le w$$$), count images with such bounding box, and sum all these values up.
An image has a bounding box of size exactly $$$h' \times w'$$$ if and only if:
• it fits inside an $$$h' \times w'$$$ rectangle;
• it has a light on each of its four borders.
To account for the second condition, we can use inclusion-exclusion principle. This way, we will have an "it does not have a light on some of its borders" condition instead, at the cost of an extra $$$2^4$$$ time factor. We will disregard this condition in the rest of this tutorial.
There are $$$2^{h'w'}$$$ possible images fitting in an $$$h' \times w'$$$ rectangles. How many of them are impossible to show because of broken lights? Let's find this number and subtract it.
Consider all possible ways to place a rectangle of size $$$h' \times w'$$$ on the given $$$h \times w$$$ grid:
• If there are no broken lights inside, any image of size $$$h' \times w'$$$ is possible to show, so we don't need to subtract anything for this size at all.
• If there is $$$1$$$ broken light inside, its relative position in the $$$h' \times w'$$$ rectangle must be turned on (for an image to be impossible to show).
• If there are $$$2$$$ broken lights inside, find their relative positions in the $$$h' \times w'$$$ rectangle. For an image to be impossible to show, at least one of the two positions must be turned on.
Unless a placement with no broken lights exists, we have some cells in the rectangle where the light must be turned on — let's call the set of these cells $$$X$$$, and some pairs of cells where at least one light must be turned on — let's call the set of these pairs $$$Y$$$.
If a pair from $$$Y$$$ contains a cell from $$$X$$$, this pair can be removed from $$$Y$$$. Once we do that, note that the pairs from $$$Y$$$ form several chains — that happens because the coordinate-wise distance between the cells in each pair is equal to the distance between the broken lights, which is $$$(r_2 - r_1, c_2 - c_1)$$$.
If we have a chain of length $$$p$$$, it can be seen that there are $$$f(p)$$$ ways to turn lights on so that every pair of neighboring cells has at least one light, where $$$f(p) = f(p - 1) + f(p - 2)$$$ are Fibonacci numbers.
Thus, the number to subtract is the product of:
• $$$2^w$$$, where $$$w$$$ is the number of cells not included in $$$X$$$ and $$$Y$$$;
• $$$f(p)$$$ over all chains formed by $$$Y$$$, where $$$p$$$ is the length of a chain.
Every subgrid size $$$h' \times w'$$$ is processed in $$$O(hw)$$$ time, and there are $$$hw$$$ different sizes, thus, the overall time complexity is $$$O(h^2 w^2)$$$.
It is possible to optimize the constant factor of this solution to pass the hard version too. However, a solution of $$$O(h w^2)$$$ time complexity exists as well. Here is a sketch of it:
• Instead of fixing both dimensions of the lights image, $$$h'$$$ and $$$w'$$$, let's only fix $$$w'$$$.
• Use inclusion-exclusion like described at the beginning of this tutorial; however, only use it for the top, left, and right borders. We will not use it for the bottom border, since we are not fixing the height of the image.
• Go through all top-left corners $$$(i, j)$$$ of the lights image in lexicographic order ($$$1 \le i \le h; 1 \le j \le w - w' + 1$$$).
• For each top-left corner, count how many images of width $$$w'$$$ can be shown using this top-left corner, which can not be shown using any previous top-left corner.
• Similarly to the previous solution, consider cases of $$$0$$$, $$$1$$$, and $$$2$$$ broken lights inside the current subgrid. Note, however, that we are not fixing the height of the subgrid, so just assume that it stretches all the way down to the bottom border of the whole grid.
• Maintain the set of cells $$$X$$$ using an array, and maintain the set of pairs $$$Y$$$ using linked lists.
• Once a cell joins set $$$X$$$, remove all pairs that touch it from set $$$Y$$$. Once a pair joins set $$$Y$$$, if neither of its ends belongs to $$$X$$$, merge two corresponding linked lists.
• Maintain a variable denoting the product of $$$f(p)$$$ over all chains formed by $$$Y$$$. Once any split or merge happens to the lists, update this variable using $$$O(1)$$$ multiplications/divisions.
• Whenever $$$i$$$ (the row number of the top-left corner) increases by $$$1$$$, the maximum available height of the lights image decreases by $$$1$$$. Thus, we have to "remove" the cells in the current bottom row: that is, for any future image, we won't be able to light up those cells. If any such cell belongs to $$$X$$$, just stop: we won't get any new images. Otherwise, if such a cell belongs to a pair in $$$Y$$$, add the second end of this pair to $$$X$$$.
• For fixed width $$$w'$$$ and for each top-left corner $$$(i, j)$$$, we need to spend $$$O(1)$$$ time. Moreover, for fixed width $$$w'$$$, once $$$i$$$ increases (which happens $$$O(h)$$$ times), we need to spend $$$O(w)$$$ time to process cell removals. Hence, the time complexity of both parts is $$$O(h w^2)$$$.