Lối đi trong kho

Bối cảnh và bài toán

Kho có n x m ô. Robot xuất phát ở góc trên trái, chỉ đi xuống hoặc sang phải. Ô # bị khóa, ô . đi được.

Yêu cầu

Đếm số đường đến góc dưới phải modulo 10^9+7.

Input

Dòng 1: n m, sau đó n dòng lưới.

Output

In số đường hợp lệ modulo 10^9+7.

Ràng buộc

• 1 <= n,m <= 1000

Chấm điểm

Ví dụ 1

Input

3 4
....
.#..
....

Output

4

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

2 2
.#
#.

Output

0

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Gợi ý

Trước khi code, hãy viết rõ ý nghĩa của trạng thái, các trạng thái tiền nhiệm và thứ tự tính sao cho mọi dependency đã có giá trị.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from AtCoder Educational DP Contest H – Grid 1. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.