$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

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$입니다.