Đường Đi Trên Lưới

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho lưới ô vuông kích thước $n \times n$ . Một số ô chứa bẫy và không thể đi qua. Hãy đếm số đường đi từ ô trái trên $(1, 1)$ đến ô phải dưới $(n, n)$ , chỉ được di chuyển sang phải hoặc xuống dưới.

In ra kết quả theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ .

$n$ dòng tiếp theo, mỗi dòng chứa $n$ ký tự: . là ô trống, * là ô bẫy.

Dữ liệu ra

In ra số đường đi hợp lệ, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 1000$

Ví dụ

Input	Output	Giải thích
10 .......... .......... .......... .......... .......... .......... .......... .......... .......... ..........	48620	Lưới $10 \times 10$ không có bẫy, số đường đi là $(\binom{18}{9}) = 48620$

Bình luận

Không có bình luận tại thời điểm này.