CSES - Grid Paths | Đường đi trên lưới

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , nhphucqt
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Xét một lưới ô vuông kích thước \(n \times n\), trong đó một số ô có thể có bẫy. Ta không được phép đi qua một ô có bẫy.

Hãy tính số lượng đường đi từ góc trên trái đến góc dưới phải của lưới, biết rằng ta chỉ được đi sang phải hoặc đi 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.
  • \(n\) dòng sau, mỗi dòng chứa \(n\) kí tự mô tả lưới: . biểu thị một ô trống và * biểu thị một cái bẫy.

Output

  • In ra một số nguyên duy nhất là số lượng đường đi chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

  • \(1 \leq n \leq 1000\)

Example

Sample input

4  
....  
.*..  
...*  
*...

Sample output

3

Bình luận