你参加了新武器的测试。为了进行测试,创建了一个多边形。多边形是一个大小为 n × m 的矩形区域,分为大小为 1 × 1 的单位正方形。该多边形包含k个对象,每个对象都是一个有边的矩形,与多边形边平行,并且完全占据几个单位正方形。对象不相交,也不相互接触。
该武器的工作原理是高度机密。你只知道可以用它来敲击任何面积不等于0且边长与多边形各边平行的矩形区域。该区域必须完全覆盖多边形所划分的一些单位正方形,并且不能接触其他正方形。当然,该区域不能跨越多边形边界。你的任务如下:你应该击中不少于1个且不多于3个的矩形物体。每个物体必须要么完全位于该区域内(在这种情况下,它被视为被击中),要么完全位于该区域外。
求击球方式的数量。
输入
第一行有三个整数 n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — 分别是多边形的大小和其上对象的数量。接下来的 n 行每行包含 m 个符号并描述多边形。符号“*”代表一个方块占据了一个物体,而符号“.”代表一个方块占据了一个物体。代表一个空的空间。符号“*”恰好构成了满足任务要求的k个矩形连通区域。
输出
输出一个数字——击中目标的不同方式的数量。
示例
输入 #1
3 3 3 *.* ... *..
输出 #1
21
输入 #2
4 5 4 .*.** ...** **... ...**
输出 #2
38
输入 #3
2 2 1 .* ..
输出 #3
4