SPOJ in Gyumri

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

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

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

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

Входные данные.

   Первая строка содержит три целых числа, разделенные одиночными пробелами N, M  (2 ≤ N, M ≤ 1000) и L (2 ≤ L ≤ 10⁹) соответственно.

   Следующие N строк содержат строковые величины, состоящие из M символов,  описывающих парк, j-й символ в i-й по счету строковой величине описывает тип квадрата. Символ ‘.’(ASCII 46) – квадрат с координатами (i, j) является пустым,  символ ‘#’(ASCII 35) – квадрат с координатами (i, j) содержит дерево.

Выходные данные.

   Содержать одно целое число – количество различных способов построения конькобежной трассы.

Примеры.