Đường đi trên lưới

Trong một buổi huấn luyện, FullHouse Dev được huấn luyện viên giao cho một bài toán thú vị về tìm đường đi trên lưới.

Bài toán

Xét một lưới ô vuông kích thước \(n \times n\) với một số ô có chứa bẫy. Bạn không được phép di chuyển vào ô có bẫy. Nhiệm vụ của FullHouse Dev là tính số đường đi từ ô trên cùng bên trái đến ô dưới cùng bên phải. Tại mỗi bước, bạn chỉ có thể di chuyển sang phải hoặc xuống dưới.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\): kích thước của lưới.
• \(n\) dòng tiếp theo mô tả lưới. Mỗi dòng có \(n\) ký tự: dấu . biểu thị ô trống, và dấu * biểu thị ô có bẫy.

OUTPUT FORMAT:

• In ra số lượng đường đi khả thi theo modulo \(10^9+7\).

Ràng buộc:

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

Ví dụ

INPUT

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

OUTPUT

3

Giải thích

Có 3 đường đi khả thi từ ô trên cùng bên trái đến ô dưới cùng bên phải, tránh các ô có bẫy (được đánh dấu bằng *). Các đường đi này phải di chuyển theo hướng phải hoặc xuống và không được đi qua các ô có bẫy.