CUBE-161: Frenemy

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli mod = 1e9 + 7;
lli dp[1001][1001][4];

int main(){

    int n;
    scanf("%d", &n);

    char ar[n+1][n+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf(" %c", &ar[i][j]);
        }
    }

    /// TopL_BotR
        /// (1, 1) -> (n, n)
        /// TopL_BotR[i][j][1] = TopL_BotR[i][j-1][1] + TopL_BotR[i-1][j][1]
        dp[1][1][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(ar[i][j] == '0' or (i == 1 and j == 1)) continue;
                dp[i][j][0] = (dp[i][j-1][0] + dp[i-1][j][0]) % mod;
            }
        }
        /// (n, n) -> (1, 1)
        /// TopL_BotR[i][j][2] = TopL_BotR[i+1][j][2] + TopL_BotR[i][j+1][2]
        dp[n][n][1] = 1;
        for(int i=n;i>=1;i--){
            for(int j=n;j>=1;j--){
                if(ar[i][j] == '0' or (i == n and j == n)) continue;
                dp[i][j][1] = (dp[i+1][j][1] + dp[i][j+1][1]) % mod;
            }
        }
    /// BotL_TopR
        /// (1, n) -> (n, 1)
        /// BotL_TopR[i][j][1] = BotL_TopR[i-1][j][1] + BotL_TopR[i][j+1][1]
        dp[1][n][2] = 1;
        for(int i=1;i<=n;i++){
            for(int j=n;j>=1;j--){
                if(ar[i][j] == '0' or (i == 1 and j == n)) continue;
                dp[i][j][2] = (dp[i-1][j][2] + dp[i][j+1][2]) % mod;
            }
        }
        /// (n, 1) -> (1, n)
        /// BotL_TopR[i][j][2] = BotL_TopR[i+1][j][2] + BotL_TopR[i][j-1][2]
        dp[n][1][3] = 1;
        for(int i=n;i>=1;i--){
            for(int j=1;j<=n;j++){
                if(ar[i][j] == '0' or (i == n and j == 1)) continue;
                dp[i][j][3] = (dp[i+1][j][3] + dp[i][j-1][3]) % mod;
            }
        }
    /// Query
    lli ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ar[i][j] == '0') continue;
            ans = ( ans + (( (dp[i][j-1][3] * dp[i][j+1][2] ) % mod) * ( (dp[i-1][j][0] * dp[i+1][j][1] ) % mod) ) % mod ) % mod;
            ans = ( ans + (( (dp[i][j-1][0] * dp[i][j+1][1] ) % mod) * ( (dp[i-1][j][2] * dp[i+1][j][3] ) % mod) ) % mod ) % mod;
        }
    }

    printf("%lld", ans);

    return 0;
}