Lưới có bước chéo

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

Robot di chuyển trong lưới ô mở/khóa. Từ một ô có thể sang phải, xuống dưới hoặc chéo xuống-phải đúng một ô.

Yêu cầu

Đếm số đường từ đầu đến cuối modulo 10^9+7.

Input

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

Output

In số đường.

Ràng buộc

• 1 <= n,m <= 1000

Chấm điểm

Ví dụ 1

Input

3 3
...
...
...

Output

13

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

2

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.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.