Xét một lưới N x N mà các ô vuông có thể có bẫy. Không được phép di chuyển vào ô 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 (ô (1, 1)) đến ô dưới cùng bên phải (ô (N, N)). Bạn chỉ có thể di chuyển sang phải hoặc 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 (1 <= N <= 1000).
N dòng tiếp theo mô tả lưới. Mỗi dòng có N ký tự: . là ô trống, và * là ô có bẫy.

Output

In ra số đường đi modulo 10^9 + 7.

Example

input
4
....
.*.*
*...
....

output
3