Настройки поиска

Администрация города Байттауна решила построить конькобежную трассу в центральном парке, который представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м2. Другими словами парку соответствует прямоугольная таблица с N строками и M столбцами.  Строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы. Следовательно, каждому квадрату можно поставить в соответствие пару числа (X, Y), где
X – это номер строки, а Y – номер столбца, на пересечении которых  он находится.
Все квадраты парка делятся на два типа: содержащие дерево либо не содержащие дерево (пустой квадрат).  Будем считать, что если квадрат содержит дерево, то  оно занимает всю его площадь.

Длиной трассы будем считать количество квадратов, через которые проходит трасса. Конькобежная трасса должна иметь квадратную форму, причем её длина должна быть не меньше L метров, а ширина – ровно один метр. Границы трассы должны быть параллельны границам парка и проходить по линиям, которые разделяют его на квадраты. Трасса не может проходить через квадраты, которые содержат деревья. На рисунке выше приведен пример трех возможных размещений трассы.
Вам даны числа N, M, L, описание всех квадратов парка, то есть для каждого из квадратов известно, пустой он или нет. Вам требуется по заданным исходным данным определить количество различных способов построения конькобежной трассы. Способы считаются различными, если им соответствуют различные множества квадратов.

n <= 1000
m <= 1000
l <= 10^9