该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个 $n \times m$ 的网格图，其中 . 表示空地，# 表示障碍物。

你需要选出恰好两个不同的障碍物，将它们变成空地，使得操作完成后，节点 $(1,1)$ 和 $(n,m)$ 恰好通过空地四联通，保证初始时 $(1,1)$ 和 $(n,m)$ 不为障碍物，请你输出方案数。

输入格式

输入第一行，包含 $2$ 个正整数 $n,m$。

之后 $n$ 行，每行包含 $m$ 个字符，描述网格图的形态。

输出格式

输出一行，表示答案。

样例输入1

3 5
..#..
.##..
..##.

样例输出1

7

样例输入2

6 6
.####.
....#.
.####.
.#....
.####.
....#.

样例输出2

78

样例输入3

10 10
.####.....
....#.....
.####.....
.#........
.####.....
....#.....
#####.....
...#......
..........
#####.....

样例输出3

208

样例输入4

见下发文件。

样例输出4

见下发文件。

评测数据规模

对于 $20\%$ 的数据，$1 \leq n,m \leq 20$。

对于 $40\%$ 的数据，$1 \leq n,m \leq 50$

对于所有测评数据，$1 \leq n,m \leq 1000$。