ВКОШП: ВКОШП 2021

Сегодня Юрик с огромной радостью встал с утра пораньше, ведь по расписанию первый урок в школе — технология! Это любимый урок Юрика, на котором он обычно игнорировал учителя и играл с друзьями в настольные игры на задней парте. Но каково было его разочарование, когда выяснилось, что сегодня на уроке состоится контрольная работа.

В самом начале урока учитель раздал каждому из школьников, включая Юрика, прямоугольную доску размера \(N \times M\). При помощи нарисованных карандашом линий вся доска разделена на \(N\) строк и \(M\) столбцов. Таким образом, доска состоит из \(N \cdot M\) квадратных клеток размера \(1 \times 1\).

Контрольная работа заключается в том, чтобы вырезать из доски некоторое количество клеток, воспользовавшись лобзиком, так, чтобы оставшаяся часть доски была красивой .

Доска называется красивой , если выполнены следующие пять условий:

1. Левая верхняя клетка исходной доски не была вырезана.
2. Правая нижняя клетка исходной доски не была вырезана.
3. Получившаяся доска является связной областью клеток. Это значит, что из любой клетки можно попасть в любую другую клетку за некоторое количество шагов, если за один шаг можно переместиться в соседнюю клетку слева, справа, сверху или снизу.
4. Для любой строки получившейся доски верно, что все клетки, находящиеся в данной строке, которые не были вырезаны, образуют непрерывный отрезок клеток по горизонтали.
5. Для любого столбца получившейся доски верно, что все клетки, находящиеся в данном столбце, которые не были вырезаны, образуют непрерывный отрезок клеток по вертикали.

Любая доска, не удовлетворяющая хотя бы одному из условий, называется некрасивой .

Так как Юрик никогда не слушал учителя технологии и увлекался математикой, вместо выполнения данной работы он задумался, сколько различных красивых досок можно получить из исходной доски при помощи вырезания некоторого, возможно, нулевого, количества клеток? Две доски считаются различными, если множества вырезанных из них клеток не совпадают.

Помогите Юрику ответить на этот вопрос.