Bài 2. Đếm số đường đi tránh vật cản

Mô tả

Cho một lưới n x m. Mỗi ô là:

• . : ô trống
• # : ô bị chặn

Bạn đứng ở ô (1,1) và muốn đi tới ô (n,m). Mỗi bước chỉ được đi:

• sang phải
• xuống dưới

Hãy đếm số đường đi hợp lệ. Vì đáp án có thể rất lớn, hãy in ra theo modulo 1000000007.

Input

• Dòng đầu ghi hai số nguyên n, m.
• n dòng tiếp theo, mỗi dòng là một xâu độ dài m chỉ gồm . và #.

Output

In ra số đường đi hợp lệ modulo 1000000007.

Giới hạn

• 1 <= n, m <= 1000 nếu không có ghi chú khác.
• Dữ liệu bảo đảm phù hợp với kiểu 64-bit signed integer nếu bài yêu cầu tổng hoặc chi phí.

Subtask

• Subtask 1 (25%): 1 <= n, m <= 20.
• Subtask 2 (35%): không có ô bị chặn.
• Subtask 3 (40%): 1 <= n, m <= 2000.

Ví dụ

Input

3 3
...
.#.
...

Output

2