칸 막기

$n \times m$ 크기의 격자가 주어지고, 일부 칸은 막혀 있다.

비어 있는 서로 다른 칸 두 개를 막아서, 빈 칸만 지나며 아래 또는 오른쪽으로만 이동하는 $(1, 1)$에서 $(n, m)$으로 가는 경로가 없도록 하는 방법의 수를 구하라.

$(1, 1)$과 $(n, m)$을 막는 것도 허용된다. 두 칸은 처음부터 막혀 있을 수도 있다.

첫째 줄에 격자의 행 수와 열 수를 나타내는 정수 $n$과 $m$ ($1 \le n, m \le 3000$)이 주어진다.

이후 $n$개의 줄에는 각각 $m$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자가 '.'이면 $(i, j)$ 칸은 비어 있고, '*'이면 막혀 있다.

두 칸을 막는 방법 중, 빈 칸만 지나며 오른쪽 또는 아래로만 이동하는 $(1, 1)$에서 $(n, m)$으로 가는 경로가 없게 만드는 경우의 수를 정수 하나로 출력한다.

첫 번째 입력에서 $(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$이다.