Atcoder Educational DP Contest H - Grid 1

Xem dạng PDF

Gửi bài giải


Điểm: 0,20 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho lưới hình chữ nhật gồm ~H~ hàng và ~W~ cột. Ô ~(i,j)~ được định nghĩa là ô vuông giao giữa hàng thứ ~i~ (từ trên xuống dưới) và cột thứ ~j~ (từ trái qua phải).

Mỗi ô vuông ~(i,j)~ ~(1 \leq i \leq H, 1 \leq j \leq W)~ được biểu diễn bởi 1 kí tự ~a_{i,j}~. Nếu ~a_{i,j}~ là ., ô ~(i,j)~ là một ô rỗng. Ngược lại, nếu ~a_{i,j}~ là #, ô ~(i,j)~ chứa vật cản.

Taro sẽ bắt đầu từ ô ~(1,1)~ đi tới ô ~(H,W)~. Mỗi bước đi, Taro chỉ có thể có di chuyển từ ô hiện tại tới ô liền kề bên phải hoặc ô liền kề phía dưới, với điều kiện ô đó phải là một ô rỗng.

Xác định số đường đi mà Taro có thể đi từ ô ~(1,1)~ tới ô ~(H,W)~. Đáp án có thể rất lớn, vì vậy chỉ in ra phần dư của nó khi chia cho ~10^9 + 7~.

Input

  • Dòng đầu tiên chứa hai số nguyên ~H~ và ~W~, lần lượt là số hàng và số cột của lưới. ~(2 \leq H, W \leq 1000)~

  • Dòng thứ ~i~ trong số ~H~ dòng tiếp theo chứa ~W~ kí tự, lần lượt là ~a_{i,1}....a_{i,W}~.

Đảm bảo rằng hai ô ~(1,1)~ và ~(H,W)~ luôn là ô rỗng.

Output

Gồm một số nguyên duy nhất là phần dư của số đường đi thỏa mãn mà Taro có thể đi khi chia cho ~10^9 + 7~.

Sample 1

Input
3 4
...#
.#..
....
Output
3
Giải thích

Có ~3~ cách đi như hình sau:

Sample 2

Input
5 2
..
#.
..
.#
..
Output
0
Giải thích

Không có bất cứ cách đi nào thỏa mãn.

Sample 3

Input
5 5
..#..
.....
#...#
.....
..#..
Output
24

Sample 4

Input
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
Output
345263555

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -95
    accve4  đã bình luận lúc 26, Tháng 9, 2021, 12:48

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.