#include <bits/stdc++.h>using namespace std;const long long mod = 1e9+7;int n;char s[60][60];int dis[60],f[60];int in[60];void spfa(){    queue<int>Q;    for(int i=0;i<n;i++) f[i]=0,dis[i] = 0x7FFFFFFF;    dis[0]=0; Q.push(0); f[0]=1;    while(!Q.empty())    {        int h = Q.front(); Q.pop(); f[h]=0;        for(int i=0;i<n;i++)        {            int val = s[h][i]-‘0‘;            int to = i;            if(val==0) continue;            if(dis[h]+val<dis[to])            {                dis[to] = dis[h]+val;                if(f[to]==0)                {                    f[to]=1;                    Q.push(to);                }            }        }    }}int main(){    while(~scanf("%d",&n))    {        for(int i=0;i<n;i++) scanf("%s",s[i]);        spfa();        memset(in,0,sizeof in);        for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)            {                if(i==j) continue;                int val = s[i][j]-‘0‘;                if(val==0) continue;                if(dis[i]+val == dis[j])                {                    in[j]++;                }            }        }        long long ans=1;        for(int i=0;i<n;i++)        {            if(in[i]==0) continue;            ans = ans* (long long)in[i]%mod;        }        printf("%lld\n",ans);    }    return 0;}