CSES - Shared codeLink to this code:
https://cses.fi/paste/d5d85fe7f661fdba3fd8f3/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 999999999999999999
ll N;
char s[1005][1005];
ll arr[1005][1005];
ll path(ll i,ll j)
{
if(s[i][j]=='*')
{
return 0;
}
if(i==N&&j==N)
{
return 1;
}
if(i>N||j>N)
{
return 0;
}
if(arr[i][j]!=-1)
{
arr[i][j]%=10000007;
return arr[i][j];
}
ll res1=path(i,j+1);
//res1=res1%10000007;
ll res2=path(i+1,j);
//res2=res2%10000007;
arr[i][j]=res1+res2;
arr[i][j]%=10000007;
return arr[i][j];
}
void solve()
{
ll i,j,k,m;
cin>>N;
for(i=1;i<=N;++i)
{
for(j=1;j<=N;++j)
{
cin>>s[i][j];
}
}
memset(arr,-1,sizeof(arr));
cout<<path(1,1)<<endl;
return ;
}
int main()
{
ll i,j,k,n,m,t;
solve();
return 0;
}