570E - Pig and Palindromes - CodeForces Solution

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1000000007;

void CF570E(istream& _r, ostream& out) {
    int n, m;
    _r >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        _r >> a[i];
    }
    if (a[0][0] != a[n-1][m-1]) {
        out << 0;
        return;
    }

    vector<vector<int>> f(n + 1, vector<int>(n + 2));
    f[1][n] = 1;
    for (int i = 1; i < (n + m) / 2; i++) {
        for (int r1 = n; r1 > 0; r1--) {
            for (int r2 = 1; r2 <= n; r2++) {
                int c1 = i + 2 - r1, c2 = m + n - i - r2;
                if (0 < c1 && c1 <= m && 0 < c2 && c2 <= m) {
                    if (a[r1 - 1][c1 - 1] == a[r2 - 1][c2 - 1]) {
                        f[r1][r2] = (((f[r1][r2] + f[r1][r2 + 1]) % mod + f[r1 - 1][r2 + 1]) % mod + f[r1 - 1][r2]) % mod;
                    } else {
                        f[r1][r2] = 0;
                    }
                }
            }
        }
    }

    int64_t ans = 0;
    if ((n + m) % 2 > 0) {
        for (int i = 1; i <= n; i++) {
            ans += int64_t(f[i][i] + f[i][i + 1]);
        }
    } else {
        for (int i = 1; i <= n; i++) {
            ans += int64_t(f[i][i]);
        }
    }
    out << ans % mod;
}

int main() {
    CF570E(cin, cout);
    return 0;
}