GRID3


Submit solution

Points: 13
Time limit: 1.0s
Memory limit: 512M

Problem type

Cho một lưới ô vuông có kích thước \(n×n\) , ô \((i,j)\) chứa ký tự \('.'\) là ô tự do, \('*'\) là ô vật cản.

Cần di chuyển từ ô \((1,1)\) sang ô \((n,n)\). Trên mỗi bước, bạn có thể di chuyển sang phải một ô hoặc xuống dưới 1 ô. Bạn không thể di chuyển đến một ô có chướng ngại vật.

Yêu cầu: Tính tổng số cách có thể di chuyển từ ô \((1,1)\) đến ô \((n,n)\) theo quy tắc trên.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n(1≤n≤10^3 ).\)

  • \(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ị chướng ngại vật.

Output

  • Một dòng duy nhất chứa tổng số cách di chuyển sau khi modulo cho \(10^9+7.\)

Sample Input

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

Sample Output

3

Comments

There are no comments at the moment.