Xét một lưới \(N \times N\) mà các ô vuông có thể có bẫy. Không được phép di chuyển vào ô có bẫy.
Nhiệm vụ của bạn là tính số đường đi từ ô trên cùng bên trái (ô \((1, 1)\)) đến ô dưới cùng bên phải (ô \((N, N)\)). Bạn chỉ có thể di chuyển sang phải hoặc xuống dưới.
Input
- Dòng đầu tiên chứa một số nguyên \(N\): kích thước của lưới (\(1 \le N \le 1000\)).
- \(N\) dòng tiếp theo mô tả lưới. Mỗi dòng có \(N\) ký tự:
.là ô trống, và*là ô có bẫy.
Output
- In ra số đường đi modulo \(10^9+7\).
Example
Test 1
Input
4
....
.*.*
.*..
....Output
3
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.