Given an N×N grid of fields (1≤N≤500), each labeled with a letter in the alphabet. For example:

ABCD

BXZX
CDXB
WCBA

Each day, Susa walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Susa keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked.

Please help Susa determine the number of distinct routes she can take that correspond to palindromes. Different ways of obtaining the same palindrome count multiple times. Please print your answer modulo 1,000,000,007.

The first line of input contains N, and the remaining N lines contain the N rows of the grid of fields. Each row contains N characters that are in the range A...Z.

Please output the number of distinct palindromic routes Susa can take, modulo 1,000,000,007.

Susa can make the following palindromes

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef __int64 ll;
const int mod=1e9+7;
char s[502][502];
ll dp[502][502][2];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%s",s[i]+1);
    int now=1,pre=0;
    if(s[1][1]!=s[n][n]) {
        return 0,printf("0\n");
    }
    dp[1][n][pre]=1;
    for(int k=2; k<=n; k++) {
        for(int i=1; i<=k; i++)
            for(int j=n; j>=i&&j>=n-k+1; j--) {
                if(s[i][k-i+1]==s[j][n-k+n-j+1])
                    dp[i][j][now]=(dp[i-1][j][pre]+dp[i][j][pre]+dp[i][j+1][pre]+dp[i-1][j+1][pre])%mod;
                else dp[i][j][now]=0;
            }
        swap(now,pre);
    }
    ll ans=0;
    for(int i=1; i<=n; i++) {
        ans=(ans+dp[i][i][pre])%mod;
    }
    printf("%lld",ans);
    return 0;
}