CF39K.Testing

You take part in the testing of new weapon. For the testing a polygon was created. The polygon is a rectangular field n × m in size, divided into unit squares 1 × 1 in size. The polygon contains k objects, each of which is a rectangle with sides, parallel to the polygon sides and entirely occupying several unit squares. The objects don't intersect and don't touch each other.

The principle according to which the weapon works is highly secret. You only know that one can use it to strike any rectangular area whose area is not equal to zero with sides, parallel to the sides of the polygon. The area must completely cover some of the unit squares into which the polygon is divided and it must not touch the other squares. Of course the area mustn't cross the polygon border. Your task is as follows: you should hit no less than one and no more than three rectangular objects. Each object must either lay completely inside the area (in that case it is considered to be hit), or lay completely outside the area.

Find the number of ways of hitting.

你参与一种新型武器的测试。为进行测试，专门建造了一个试验场。该试验场是一个大小为 $n \times m$ 的矩形场地，被划分为若干个 $1 \times 1$ 的单位正方形。场地上共放置了 $k$ 个物体，每个物体均为一个边与试验场边界平行的矩形，且完全覆盖若干个单位正方形。这些物体互不相交，也互不接触。

该武器的工作原理高度保密。你仅知：可使用该武器攻击任意一个面积非零、边与试验场边界平行的矩形区域；该区域必须完全覆盖若干个单位正方形（即其边界必须与单位正方形的边重合），且不能与任何其他单位正方形相交（即不能“部分覆盖”某个单位正方形）；当然，该区域也不能超出试验场边界。

你的任务如下：所选攻击区域必须恰好击中不少于一个、不多于三个的矩形物体；且对每个物体而言，它必须完全位于该攻击区域内（此时视为被击中），或完全位于该攻击区域外（即不允许有任何物体部分位于区域内、部分位于区域外）。

求满足条件的攻击方式总数。

The first line has three integers n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — the sizes of the polygon and the number of objects on it respectively. Next n lines contain m symbols each and describe the polygon. The symbol "*" stands for a square occupied an object, whereas the symbol "." stands for an empty space. The symbols "*" form exactly k rectangular connected areas that meet the requirements of the task.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 90$），分别表示多边形的尺寸以及其上的物体数量。接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述该多边形。字符 * 表示一个被物体占据的方格，而字符 . 表示一个空格。所有 * 字符恰好构成 $k$ 个矩形连通区域，且这些区域满足题目要求。

Output a single number — the number of different ways to hit a target.

输出一个数字——击中目标的不同方式的数量。