CCCPaste

dabb473394251

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1004;
const int INF = 2e9;
const ll MOD = 1e9 + 7;
int n, m;
char mat[maxn][maxn];
ll dp[maxn][maxn];

ll rec(int i, int j) {
if(i == n - 1 and j == m - 1) {
return 1;
}
if(dp[i][j] != -1) {
return dp[i][j];
}

ll res = 0;
if(i + 1 < n and mat[i + 1][j] != '*') {
res += rec(i + 1, j);
res %= MOD;
}
if(j + 1 < m and mat[i][j + 1] != '*') {
res += rec(i, j + 1);
res %= MOD;
}


dp[i][j] = res;
return res;
}
int main()
{
cin >> n;
m = n;

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
if(mat[0][0] == '*') {
cout << 0 << endl;
return 0;
}
memset(dp, -1, sizeof dp);
cout << rec(0, 0) << endl;
return 0;
}

// 345263555
// 35345263800