Grid Paths

#include <iostream>
#include <vector>

using namespace std;
typedef long long LL;

vector<vector<LL> > A;

int main(){
    LL mod = 1e9 + 7;
    LL n; cin >> n;
    for(LL i = 0; i < n; i++){
	    vector<LL> row;
        for(LL j = 0; j < n; j++){
            LL x; cin >> x; row.push_back(x);
        }
        A.push_back(row);
	}

    vector<vector<LL> > to(n, vector<LL>(n));
    vector<vector<LL> > from(n, vector<LL>(n));

    for(LL i = 0; i < n; i++){
        to[0][i] = 1;
        to[i][0] = 1;
        from[i][n-1] = 1;
        from[n-1][i] = 1;
    }

    for(LL i = 1; i < n; i++){
        for(LL j = 1; j < n; j++){
            to[i][j] = (to[i-1][j] + to[i][j-1]) % mod;
        }
    }

    for(LL i = n-2; i >= 0; i--){
        for(LL j = n-2; j >= 0; j--){
            from[i][j] = (from[i+1][j] + from[i][j+1]) % mod;
        }
    }

    LL ans = 0;
    for(LL i = 0; i < n; i++){
        for(LL j = 0; j < n; j++){
            ans = ans + (((from[i][j] * to[i][j]) % mod) * A[i][j]) % mod;
            ans %= mod;
        }
    }

    cout << ans << endl;

}

Test 1

Verdict: ACCEPTED