Bạn được cho một lưới $n \times m$, trong đó một số ô đã bị chặn.

Bạn cần tìm số cách chặn thêm hai ô trống khác nhau sao cho không còn đường đi từ $(1, 1)$ đến $(n, m)$ chỉ bằng cách di chuyển sang phải hoặc xuống dưới qua các ô trống.

Lưu ý rằng việc chặn các ô $(1, 1)$ và $(n, m)$ không bị cấm. Các ô này cũng có thể đã bị chặn từ trước.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 3000$): số hàng và số cột trong lưới.

Mỗi dòng trong $n$ dòng tiếp theo chứa $m$ ký tự, trong đó ký tự thứ $j$ của chuỗi thứ $i$ bằng '.' nếu ô $(i, j)$ là ô trống và '*' nếu nó đã bị chặn.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách chặn hai ô trống sao cho không còn đường đi từ $(1, 1)$ đến $(n, m)$ chỉ bằng cách di chuyển sang phải hoặc xuống dưới qua các ô trống.

Ví dụ

Dữ liệu vào 1

3 3
...
...
...

Dữ liệu ra 1

17

Ghi chú

Trong ví dụ đầu tiên, nếu bạn chặn $(1, 1)$ hoặc $(3, 3)$ và bất kỳ ô nào khác, sẽ không còn đường đi hợp lệ. Số cách như vậy là $8 + 8 - 1$.

Ngoài ra, nếu bạn chặn $((1, 2)$ và $(2, 1))$ hoặc $((3, 2)$ và $(2, 3))$ thì cũng sẽ không còn đường đi hợp lệ, vì vậy đáp án là $8 + 8 - 1 + 2 = 17$.

Dữ liệu vào 2

3 3
.**
.*.
...

Dữ liệu ra 2

15

Ghi chú

Trong ví dụ thứ hai, nếu bạn chặn bất kỳ hai ô nào, sẽ không còn đường đi, vì vậy đáp án là $\binom{6}{2} = 15$.

Dữ liệu vào 3

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

Dữ liệu ra 3

6

Ghi chú

Trong ví dụ thứ ba, ban đầu đã không có đường đi từ $(1, 1)$ đến $(n, m)$, vì vậy sau khi chặn bất kỳ hai ô nào thì vẫn sẽ không có đường đi, do đó đáp án là $\binom{4}{2} = 6$.