GRID3
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