$n \times m$ のグリッドが与えられ、いくつかのセルは既にブロックされています。

$(1, 1)$ から $(n, m)$ への、右または下への移動のみを用いた自由なセル（ブロックされていないセル）を通るパスが存在しなくなるように、2つの異なる自由なセルをブロックする方法の数を求めてください。

$(1, 1)$ や $(n, m)$ をブロックすることは禁止されていません。これらは最初からブロックされている可能性もあります。

入力

1行目には、グリッドの行数と列数を表す2つの整数 $n$ と $m$ ($1 \le n, m \le 3000$) が与えられます。 続く $n$ 行の各行には $m$ 文字が含まれており、各行の $j$ 番目の文字は、セル $(i, j)$ が自由な場合は '.'、ブロックされている場合は '*' となります。

出力

$(1, 1)$ から $(n, m)$ への、右または下への移動のみを用いた自由なセルを通るパスが存在しなくなるような、2つのセルをブロックする方法の数を1つの整数で出力してください。

入出力例

入力 1

3 3
...
...
...

出力 1

17

入力 2

3 3
.**
.*.
...

出力 2

15

入力 3

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

出力 3

6

注記

最初の例では、$(1, 1)$ または $(3, 3)$ と他の任意のセルをブロックすれば、正しいパスは存在しなくなります。そのような方法の数は $8 + 8 - 1$ 通りです。 また、$(1, 2)$ と $(2, 1)$ をブロックした場合、あるいは $(3, 2)$ と $(2, 3)$ をブロックした場合も正しいパスは存在しなくなるため、答えは $8 + 8 - 1 + 2 = 17$ となります。

2番目の例では、任意の2つのセルをブロックすればパスは存在しなくなるため、答えは $\binom{6}{2} = 15$ となります。

3番目の例では、最初から $(1, 1)$ から $(n, m)$ へのパスが存在しないため、任意の2つのセルをブロックした後もパスは存在せず、答えは $\binom{4}{2} = 6$ となります。