K. Испытания
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Вы участвуете в испытаниях нового оружия. Для испытаний создан полигон, представляющий собой прямоугольное поле размера n × m, разделенное на единичные квадраты 1 × 1. На полигоне расположено k объектов, каждый из которых является прямоугольником со сторонами, параллельными сторонам полигона, занимающим полностью несколько единичных квадратов. Объекты не пересекаются и не касаются друг друга.

Принцип действия оружия сверхсекретен. Вам известно лишь то, что с помощью него можно нанести удар по любой прямоугольной области ненулевой площади со сторонами, параллельными сторонам полигона. Область должна накрывать полностью некоторые из единичных квадратов, на которые разбит полигон, и никак не затрагивать остальные квадраты. Разумеется, область не должна выходить за границы полигона. При этом вам поставлена задача: поразить не менее одного и не более трех прямоугольных объектов. Каждый объект должен лежать либо целиком внутри области (тогда он считается пораженным), либо целиком вне области.

Посчитайте количество способов нанести удар.

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

В первой строке содержатся три целых числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — размеры полигона и количество объектов на нем, соответственно. Следующие n строк содержат по m символов каждая и описывают полигон. Символ «*» означает, что соответствующий квадрат на полигоне занят объектом, символ «.» обозначает пустое пространство. Гарантируется, что символы «*» образуют ровно k связных прямоугольных областей, отвечающих условию задачи.

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

Выведите единственное число — количество способов нанести удар.

Примеры
Входные данные
3 3 3
*.*
...
*..
Выходные данные
21
Входные данные
4 5 4
.*.**
...**
**...
...**
Выходные данные
38
Входные данные
2 2 1
.*
..
Выходные данные
4