Từ tháng 10/2004 đến năm 2005, các lập trình viên của Google đang phát triển một ứng dụng mang tên Google Map.

Việc xây dựng nên ứng dụng Google Map này để phục vụ cho việc xem xét vị trí, bản đồ và tìm đường đi.

Nhưng có một vấn đề đã xảy ra, người dùng đôi lúc không muốn đi những tuyến đường ngắn nhất vì có thể do địa hình, đường đi.

Vậy nên các nhà sáng lập cần xây dựng một Google Map có thể gợi ý cho người dùng những đường đi có thể đi được từ A -> B.

Việc của họ bây giờ là xác định xem từ A -> B có bao nhiêu con đường đi đến.

ĐẦU VÀO

Dòng đầu tiên, nhập n: Cỡ của ma trận vuông \(n\) < \(1000\)

Các dòng tiếp theo là các ma trận vuông thể hiện con đường và các chướng ngoại vật (Với quy ước: *: tường, #: hàng rào, _: đường đang thi công, .: đường đi được)

ĐẦU RA

In ra một dòng số con đường đi được từ đỉnh A -> B, biết rằng:

• A là điểm bên trái trên cùng
• B là điểm bên phải dưới cùng
• Và để tối ưu nhất thì thuật toán sẽ chỉ gợi ý cho những con đường đi theo hướng từ trái sang phải, từ trên xuống dưới và tường, hàng rào, đường đang thi công sẽ không được gợi ý đi qua.

• Vì số quá lớn nên lấy dư cho \(1000000007\)

  VÍ DỤ

  Input

3
..*
..#
...

Output

3

Giải thích

3 con đường là :

(1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3)

(1,1) -> (2,1) -> (2,2) -> (3,2) -> (3,3)

(1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)