Беговая дорожка

Байт-таун является столицей Байтландии. Это очень красивый и богатый город в центре страны. Архитектура и природа поражает воображение. Каждый год количество туристов, приезжающих погостить в этот чудный год, неуклонно увеличивается.

Центральный парк является главной достопримечательностью Байт-тауна. Парк представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м². Таким образом, парк – это прямоугольная таблица с N строками и M столбцами. Строки нумеруются сверху вниз начиная с единицы, столбцы нумеруются слева направо начиная с единицы. Следовательно, каждой ячейке (квадрату) можно поставить в соответствие уникальную пару числа (X, Y), где X – это номер строки, а Y – номер столбца, на пересечении которых находится данный квадрат.

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

Рисунок №1. Описание второго примера.

В целях оздоровления нации администрация Байт-тауна решила построить в парке беговую дорожку прямоугольной формы длинной S метров и шириной один метр. Дорожка должна вписываться в структуру парка, то есть границы дорожки должны быть параллельны границам парка и проходить по границам парка, которые разделяют его на квадраты. Однако экологи Байтландии строго-настрого запретили вырубку деревьев, что существенно ограничивает свободу выбора размещения дорожки, так как дорожка может проходить только через свободные квадраты. На рисунке выше приведен пример двух из 11 возможных размещений беговой дорожки.

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