Robot Bit đứng ở ô trên cùng bên trái của lưới n × m (tọa độ hàng 1, cột 1), cần đi tới ô dưới cùng bên phải (hàng n, cột m).
Sơ đồ di chuyển Robot trên lưới
Mỗi bước Robot chỉ được đi sang phải hoặc xuống dưới, và không được đi vào ô có chướng ngại vật "#". Có bao nhiêu đường đi khác nhau? In kết quả chia lấy dư cho 10^9 + 7.
Dữ liệu vào
Dòng đầu chứa n và m. n dòng tiếp theo, mỗi dòng là xâu m ký tự "." (trống) hoặc "#" (chướng ngại).
Kết quả
Số đường đi, chia lấy dư cho 10^9 + 7 (0 nếu không có đường).
Giới hạn
1 ≤ n, m ≤ 500.
Ví dụ 1 – vào
3 3 ... .#. ...
Ví dụ 1 – ra
2
Ví dụ 2 – vào
2 2 .# #.
Ví dụ 2 – ra
0