Đường Đi Trên Lưới

Cho lưới ô vuông kích thước $n\times n$. Một số ô chứa bẫy và không thể đi qua. Hãy đếm số đường đi từ ô trái trên $(1,1)$ đến ô phải dưới $(n,n)$, chỉ được di chuyển sang phải hoặc xuống dưới.

In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$.

• $n$ dòng tiếp theo, mỗi dòng chứa $n$ ký tự: . là ô trống, * là ô bẫy.

Dữ liệu ra

In ra số đường đi hợp lệ, modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 1000$

Ví dụ