Vous disposez d'une grille $n \times m$, et certaines cellules sont bloquées.

Vous devez trouver le nombre de façons de bloquer deux cellules libres distinctes de telle sorte qu'il n'y ait plus aucun chemin de $(1, 1)$ à $(n, m)$ qui se déplace uniquement vers le bas ou vers la droite en utilisant uniquement des cellules libres.

Notez qu'il n'est pas interdit de bloquer les cellules $(1, 1)$ et $(n, m)$. Elles peuvent être bloquées initialement.

Entrée

La première ligne contient deux entiers $n$ et $m$ ($1 \le n, m \le 3000$) : le nombre de lignes et de colonnes dans la grille.

Chacune des $n$ lignes suivantes contient $m$ caractères, tels que le $j$-ième caractère de la $i$-ième chaîne est égal à '.' si la cellule $(i, j)$ est libre et '*' si elle est bloquée.

Sortie

Affichez un entier : le nombre de façons de bloquer deux cellules, de telle sorte qu'il n'y ait plus aucun chemin de $(1, 1)$ à $(n, m)$ qui se déplace uniquement vers la droite ou vers le bas en utilisant uniquement des cellules libres.

Exemples

Entrée 1

3 3
...
...
...

Sortie 1

17

Entrée 2

3 3
.**
.*.
...

Sortie 2

15

Entrée 3

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

Sortie 3

6

Remarque

Dans le premier exemple, si vous bloquez $(1, 1)$ ou $(3, 3)$ et n'importe quelle autre cellule, il n'y aura plus de chemin valide. Le nombre de telles façons est $8 + 8 - 1$.

De plus, si vous bloquez $((1, 2) \text{ et } (2, 1))$ ou $((3, 2) \text{ et } (2, 3))$, il n'y aura plus de chemin valide, donc la réponse est $8 + 8 - 1 + 2 = 17$.

Dans le deuxième exemple, si vous bloquez deux cellules quelconques, il n'y aura plus de chemin, donc la réponse est $\binom{6}{2} = 15$.

Dans le troisième exemple, initialement, il n'y a aucun chemin de $(1, 1)$ à $(n, m)$, donc après avoir bloqué deux cellules quelconques, il n'y aura toujours aucun chemin, donc la réponse est $\binom{4}{2} = 6$.