Palindromic Paths

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
 
const int MAX_N = 500;
 
int main() {
	freopen("palpath.in", "r", stdin);
	freopen("palpath.out", "w", stdout);
	int n;
	cin >> n;
	string grid[MAX_N];
	for (int i = 0; i < n; i++) { cin >> grid[i]; }
	long long prev[MAX_N][MAX_N]{};
	for (int i = 0; i < n; i++) { prev[i][i] = 1; }
	for (int a = 1; a < n; a++) {
		/*
		 * dp[i][j] es la cantidad de palíndromos de longitud 2a + 1
		 * que empiezan en row1 y terminan en row2
		 * con el medio de la cadena en la diagonal
		 */
		long long dp[MAX_N][MAX_N]{};
		for (int row1 = 0; row1 < n; row1++) {
			int col1 = n - 1 - row1 - a;
			if (col1 < 0) { continue; }
			for (int row2 = 0; row2 < n; row2++) {
				int col2 = n - 1 - row2 + a;
				if (col2 >= n) { continue; }
				/*
				 * si el inicio y el final de la cadena no son iguales
				 * no es un palíndromo así que continuamos
				 */
				if (grid[row1][col1] != grid[row2][col2]) { continue; }
				dp[row1][row2] = prev[row1][row2];
				if (row1 + 1 < n) { dp[row1][row2] += prev[row1 + 1][row2]; }
				if (row2 - 1 >= 0) { dp[row1][row2] += prev[row1][row2 - 1]; }
				if (row1 + 1 < n && row2 - 1 >= 0) {
					dp[row1][row2] += prev[row1 + 1][row2 - 1];
				}
				dp[row1][row2] %= (int)(1e9 + 7);
			}
		}
		// asignar el arreglo dp actual al arreglo prev
		swap(prev, dp);
	}
	cout << prev[0][n - 1] << endl;
}