Grid Paths

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define M 1000000007
#define N (1<<18)
#define P complex<long long>
#define X real()
#define Y imag()
 
using namespace std;
 
ll n, rdk[101][101], rdk2[101][101], lah[111][111];
ll ans[101][101], tav[101][101], ans2;
 
void asd(int x, int y) {
	for(int i=0; i<=100; i++)
		for(int j=0; j<=100; j++)
			rdk2[i][j] = 0;
	rdk2[x][y-1] = 1;
	for(int i=x; i<=n; i++) {
		for(int j=y; j<=n; j++) {
			rdk2[i][j] = rdk2[i][j-1]+rdk2[i-1][j];
			rdk2[i][j] %= M;
		}
	}
	lah[x][y] = rdk2[n][n];
}
 
int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	srand(time(NULL));
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
		cin >> rdk[i][j];
	}
	tav[0][1] = 1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			asd(i,j);
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i == n && j == n) {
				tav[i][j] = tav[i][j-1]+tav[i-1][j];
				tav[i][j] %= M;
				ans[i][j] += rdk[i][j]*tav[i][j];
				ans[i][j] %= M;
				ans2 += ans[i][j];
				ans2 %= M;
				break;
			}
			tav[i][j] = tav[i][j-1]+tav[i-1][j];
			tav[i][j] %= M;
			ans[i][j] += (((tav[i][j]*lah[i+1][j]+tav[i][j]*lah[i][j+1])%M)*rdk[i][j])%M;
			ans[i][j] %= M;
				ans2 += ans[i][j];
				ans2 %= M;
		}
	}
	cout << ans2;
}

Test 1

Verdict: ACCEPTED