Bài toán:

Cho một ma trận có kích thước N x N. Mỗi ô trong ma trận chứa ký tự, trong đó . tương ứng với đường đi và * tương ứng với chướng ngại vật. Một con chuột muốn đi từ ô (1, 1) đến ô (N, N) và chỉ được di chuyển khi một ô là đường đi (ký tự .). Cần tính số lượng các cách mà chuột có thể di chuyển từ góc trên bên trái đến góc dưới bên phải, chỉ có thể di chuyển sang phải hoặc xuống dưới.

Yêu cầu: Hãy đếm số cách con chuột có thể di chuyển tới đích. Do kết quả có thể rất lớn, hãy lấy kết quả modulo ~10^9 + 7~.

Input Format:

• Dòng đầu tiên là N.
• N dòng tiếp theo, mỗi dòng chứa N ký tự, trong đó . là đường đi và * là chướng ngại vật.

Output Format:

• Số đường đi tối đa.

Constraints:

• ~ 1 \leq N \leq 1000 ~

Ví dụ:

Input:

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

Output:

3