Grid Paths

#include <iostream>
 
using namespace std;
typedef long long ll;
 
const ll M = 1000000007;
 
int n;
ll t[105][105];
 
ll dp1[105][105];
ll dp2[105][105];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> t[i][j];
        }
    }
    dp1[1][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (!(i == 1 && j == 1)) {
                dp1[i][j] = dp1[i-1][j] + dp1[i][j-1];
                dp1[i][j] %= M;
            }
        }
    }
    dp2[n][n] = 1;
    for (int i = n; i >= 1; --i) {
        for (int j = n; j >= 1; --j) {
            if (!(i == n && j == n)) {
                dp2[i][j] = dp2[i+1][j] + dp2[i][j+1];
                dp2[i][j] %= M;
            }
        }
    }
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            ll ccnt = dp1[i][j] * dp2[i][j];
            ccnt %= M;
            res += (ccnt * t[i][j]);
            res %= M;
        }
    }
    cout << res << "\n";
    return 0;
}

Test 1

Verdict: ACCEPTED