#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
vector<long long>b[3000];
priority_queue<pair<long long,long long> >q;
long long n,a[60][60],s[60][60],a1,x,y,dis[3000],f[3000],r[3000];
bool bk[3000];
inline void dfs(int p){
    bk[p]=1;
	if(b[p].size())for(int i=0;i<b[p].size();i++)f[b[p][i]]+=f[p];
	if(b[p].size())for(int i=0;i<b[p].size();i++){
		r[b[p][i]]--;
		if(r[b[p][i]]==0)dfs(b[p][i]);
	}
	return;
}
int main(){
	freopen("campus_walk.in","r",stdin);
    freopen("campus_walk.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%lld",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			s[i][j]=j+(i-1)*n;
	for(int i=1;i<=n*n-1;i++)dis[i]=999999;
	q.push(make_pair(0,n*n));
	while(q.size()){
	    a1=q.top().second;q.pop();
		x=(a1-1)/n+1;y=(a1-1)%n+1;
		if(dis[s[x-1][y]]>dis[a1]+a[x-1][y]&&s[x-1][y]!=0){
		    dis[s[x-1][y]]=dis[a1]+a[x-1][y];
			q.push(make_pair(-dis[s[x-1][y]],s[x-1][y]));
		}
		if(dis[s[x+1][y]]>dis[a1]+a[x+1][y]&&s[x+1][y]!=0){
		    dis[s[x+1][y]]=dis[a1]+a[x+1][y];
			q.push(make_pair(-dis[s[x+1][y]],s[x+1][y]));
		}
		if(dis[s[x][y-1]]>dis[a1]+a[x][y-1]&&s[x][y-1]!=0){
		    dis[s[x][y-1]]=dis[a1]+a[x][y-1];
			q.push(make_pair(-dis[s[x][y-1]],s[x][y-1]));
		}	
		if(dis[s[x][y+1]]>dis[a1]+a[x][y+1]&&s[x][y+1]!=0){
		    dis[s[x][y+1]]=dis[a1]+a[x][y+1];
			q.push(make_pair(-dis[s[x][y+1]],s[x][y+1]));
		}
	}
	for(int i=1;i<=n*n;i++)bk[i]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(s[i-1][j]!=0&&dis[s[i][j]]>dis[s[i-1][j]]){
			    b[s[i][j]].push_back(s[i-1][j]);
				r[s[i-1][j]]++;
			}
			if(s[i+1][j]!=0&&dis[s[i][j]]>dis[s[i+1][j]]){
			    b[s[i][j]].push_back(s[i+1][j]);
				r[s[i+1][j]]++;
			}
			if(s[i][j-1]!=0&&dis[s[i][j]]>dis[s[i][j-1]]){
			    b[s[i][j]].push_back(s[i][j-1]);
				r[s[i][j-1]]++;
			}
			if(s[i][j+1]!=0&&dis[s[i][j]]>dis[s[i][j+1]]){
			    b[s[i][j]].push_back(s[i][j+1]);
				r[s[i][j+1]]++;
			}
		}
	}
	f[1]=1;
	for(int i=1;i<=n*n;i++)if(!bk[i]&&r[i]==0)dfs(i);
	printf("%lld",f[n*n]);
	return 0;
}