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

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

3