Bài toán: Đếm số đường đi trong lưới có bẫy

Đề bài

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

• Ký hiệu:
  • ~ . ~: Ô trống (có thể đi vào).
  • ~ * ~: Ô chứa bẫy (không thể đi vào).

Kết quả cần lấy modulo ~ 10^9 + 7 ~.

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 tiếp theo, mỗi dòng chứa ~ n ~ ký tự:
  • ~ . ~: Ô trống.
  • ~ * ~: Ô chứa bẫy.

Output

• In ra một số nguyên: số lượng đường đi từ ô trên cùng bên trái đến ô dưới cùng bên phải (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 từ ô trên cùng bên trái đến ô dưới cùng bên phải, tránh các ô chứa bẫy.