Mô tả và yêu cầu

Cho một lưới 𝑛 × 𝑛 ô vuông. Trong đó có một số ô trống và một số ô có bẫy.

Yêu cầu: Tính số đường đi khác nhau để đi từ góc trên bên trái đến góc dưới bên phải
của ô. Ta chỉ có thể đi sang phải hoặc đi xuống dưới.

Dữ liệu vào

- Dòng đầu gồm số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 1000).
- 𝑛 dòng tiếp theo: mỗi dòng chứa 𝑛 kí tự, kí tự ’.’ tương ứng với ô trống và
kí tự ’#’ tương ứng với ô có bẫy.

Dữ liệu ra

- Một số nguyên duy nhất của bài toán chia lấy dư cho 109 + 7.

Ví dụ

Input                                        Output
         4                                            3
         ....
         .*..
         ...*
         *...