#include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define ui unsigned int

 using namespace std;

 const int modd=1e9+;

 ui f[][][];

 char mp[][],s[][];

 int i,j,k,n,m;

 int ans;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 int main(){

     n=read();

     for(i=;i<=n;i++)scanf("%s",s[i]+);

     if(s[][]!=s[n][n]){puts("");return ;}

     for(i=;i<=n+n-;i++)

         for(j=;j<=min(i,n+n-i);j++)

             if(i<=n)mp[i][j]=s[i-j+][j];

             else mp[i][j]=s[n-j+][i+j-n];

     bool now=,pre=;int nn=n+n;

     f[][][]=s[][]==s[n][n];

     for(i=;i<=n;i++,swap(now,pre))

         for(j=;j<=i;j++)for(k=;k<=i;k++)if(mp[i][j]==mp[nn-i][k])

             f[now][j][k]=(f[pre][j-][k-]+f[pre][j-][k]+f[pre][j][k-]+f[pre][j][k])%modd;

         else f[now][j][k]=;

     for(i=;i<=n;i++)ans+=f[pre][i][i],ans-=ans>=modd?modd:;

     printf("%d\n",ans);

 }