Đếm đường đi trên lưới có vật cản

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một lưới kích thước $N \times M$ gồm các ô trống . và các ô vật cản #. Bạn bắt đầu tại ô $(1, 1)$ và muốn đi đến ô $(N, M)$. Mỗi bước chỉ được đi sang phải hoặc đi xuống dưới và không được bước vào ô vật cản.

Hãy đếm số đường đi khác nhau từ $(1, 1)$ đến $(N, M)$ theo modulo $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N, M \le 1000$).
  • $N$ dòng tiếp theo, mỗi dòng gồm $M$ ký tự . hoặc #.
Dữ liệu ra

Số nguyên duy nhất là số đường đi hợp lệ modulo $10^9 + 7$.

Ví dụ
Input Output
3 3<br>...<br>.#.<br>... 2
Giới hạn
  • $1 \le N, M \le 1000$
Draft saved