Дана сетка размера $n \times m$, некоторые клетки которой заблокированы. Вам необходимо найти количество способов заблокировать две свободные различные клетки так, чтобы не осталось пути из $(1, 1)$ в $(n, m)$, проходящего только по свободным клеткам и совершающего движения только вправо или вниз. Заметьте, что блокировка клеток $(1, 1)$ и $(n, m)$ не запрещена. Они также могут быть заблокированы изначально.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 3000$): количество строк и столбцов в сетке. Каждая из следующих $n$ строк содержит $m$ символов, где $j$-й символ $i$-й строки равен «.» если клетка $(i, j)$ свободна, и «*», если она заблокирована.

Выходные данные

Выведите одно целое число: количество способов заблокировать две клетки так, чтобы не осталось пути из $(1, 1)$ в $(n, m)$, проходящего только по свободным клеткам и совершающего движения только вправо или вниз.

Примеры

Входные данные 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$. Во втором примере, если вы заблокируете любые две клетки, пути не останется, поэтому ответ равен $\binom{6}{2} = 15$. В третьем примере изначально путей из $(1, 1)$ в $(n, m)$ нет, поэтому после блокировки любых двух клеток путей по-прежнему не будет, и ответ равен $\binom{4}{2} = 6$.