题目描述

一座自动化仓库被划分成 n 行 m 列的方格区域。部分区域已经堆满货箱，无法通行；其余区域仍然空闲。

仓库里的运输机器人只能从左上角 (1, 1) 出发，最终到达右下角 (n, m)。由于轨道方向限制，机器人每一步只能向下或向右移动，并且只能经过空闲格子。

现在仓库管理员要再临时封锁两个不同的空闲格子。请你计算，有多少种选择这两个格子的方案，可以使机器人无法再从 (1, 1) 到达 (n, m)。

注意，(1, 1) 和 (n, m) 本身也可以被选作临时封锁的格子；它们也可能在输入时就已经被占据。

输入格式

第一行包含两个整数 n, m，表示仓库网格的行数和列数。

接下来 n 行，每行包含一个长度为 m 的字符串。第 i 行第 j 个字符描述格子 (i, j) 的状态：

• . 表示该格子空闲；
• * 表示该格子已经被占据。

输出格式

输出一个整数，表示选择两个不同空闲格子并将其封锁后，使得不存在从 (1, 1) 到 (n, m) 的、只向下或向右移动且只经过空闲格子的路径的方案数。

数据范围

• 1 <= n, m <= 3000

样例

样例 1

3 3
...
...
...

17

样例 2

3 3
.**
.*.
...

15

样例 3

3 4
****
....
****

6

样例说明

在第一个样例中，若封锁 (1, 1) 或 (3, 3) 中的一个，再搭配任意另一个空闲格子，都能阻断所有合法路径；此外，封锁 (1, 2) 与 (2, 1)，或封锁 (3, 2) 与 (2, 3)，也能阻断路径，因此答案为 17。

第二个样例中，无论选择哪两个空闲格子，所有可能路径都会被阻断，所以答案为 C(6, 2) = 15。

第三个样例中，一开始就不存在合法路径，因此任意选择两个空闲格子都满足要求，答案为 C(4, 2) = 6。