C. Cells Blocking
time limit per test
3 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given a grid $$$n \times m$$$, and some cells are blocked.

You need to find the number of ways to block two free different cells such that there will be no path from $$$(1,1)$$$ to $$$(n,m)$$$ which goes down or to the right by only using free cells.

Note that it is not forbidden to block cells $$$(1,1)$$$ and $$$(n,m)$$$. They may be blocked initially as well.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 3000)$$$: number of rows and columns in the grid.

Each of the next $$$n$$$ lines contain $$$m$$$ characters, such that the $$$j$$$-th character of $$$i$$$-th string is equal to '.' if cell $$$(i,j)$$$ is free and '*' if it is blocked.

Output

Print one integer: the number of ways to block two cells, such that there will be no path from $$$(1,1)$$$ to $$$(n,m)$$$ which goes only to the right or down by only using free cells.

Examples
Input
3 3
...
...
...
Output
17
Input
3 3
.**
.*.
...
Output
15
Input
3 4
****
....
****
Output
6
Note

In the first example, if you will block $$$(1,1)$$$ or $$$(3,3)$$$ and any other cell, there will be no correct path. The number of such ways is $$$8+8-1$$$.

Also, if you will block ($$$(1,2)$$$ and $$$(2,1)$$$) or ($$$(3,2)$$$ and $$$(2,3))$$$ there will be no correct path, so the answer is $$$8+8-1+2 = 17$$$.

In the second example, if you block any two cells, there will be no path, so the answer is $$$6 \choose 2$$$$$$=15$$$.

In the third example, initially, there are no paths from $$$(1,1)$$$ to $$$(n,m)$$$, so after blocking any two cells there still will be no paths, so the answer is $$$4 \choose 2$$$ $$$=6$$$.