Se te da una cuadrícula $n \times m$, y algunas celdas están bloqueadas.

Debes encontrar el número de formas de bloquear dos celdas libres distintas de tal manera que no exista ningún camino desde $(1, 1)$ hasta $(n, m)$ que se mueva solo hacia abajo o hacia la derecha utilizando únicamente celdas libres.

Ten en cuenta que no está prohibido bloquear las celdas $(1, 1)$ y $(n, m)$. Estas pueden estar bloqueadas inicialmente también.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n, m \le 3000$): el número de filas y columnas en la cuadrícula.

Cada una de las siguientes $n$ líneas contiene $m$ caracteres, donde el $j$-ésimo carácter de la $i$-ésima cadena es igual a '.' si la celda $(i, j)$ está libre y '*' si está bloqueada.

Salida

Imprime un solo entero: el número de formas de bloquear dos celdas, de tal manera que no exista ningún camino desde $(1, 1)$ hasta $(n, m)$ que se mueva solo hacia la derecha o hacia abajo utilizando únicamente celdas libres.

Ejemplos

Entrada 1

3 3
...
...
...

Salida 1

17

Entrada 2

3 3
.**
.*.
...

Salida 2

15

Entrada 3

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

Salida 3

6

Nota

En el primer ejemplo, si bloqueas $(1, 1)$ o $(3, 3)$ y cualquier otra celda, no habrá un camino correcto. El número de tales formas es $8 + 8 - 1$.

Además, si bloqueas $((1, 2)$ y $(2, 1))$ o $((3, 2)$ y $(2, 3))$ no habrá un camino correcto, por lo que la respuesta es $8 + 8 - 1 + 2 = 17$.

En el segundo ejemplo, si bloqueas cualesquiera dos celdas, no habrá camino, por lo que la respuesta es $\binom{6}{2} = 15$.

En el tercer ejemplo, inicialmente, no hay caminos desde $(1, 1)$ hasta $(n, m)$, por lo que después de bloquear cualesquiera dos celdas todavía no habrá caminos, así que la respuesta es $\binom{4}{2} = 6$.