Deleting Edges

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1693    Accepted Submission(s): 575

Problem Description

Little Q is crazy about graph theory, and now he creates a game about graphs and trees.

There is a bi-directional graph with 

n nodes, labeled from 0 to n−1. Every edge has its length, which is a positive integer ranged from 1 to 9.

Now, Little Q wants to delete some edges (or delete nothing) in the graph to get a new graph, which satisfies the following requirements:

(1) The new graph is a tree with n−1 edges.

(2) For every vertice v(0<v<n), the distance between 0 and v on the tree is equal to the length of shortest path from 0 to v in the original graph.

Little Q wonders the number of ways to delete edges to get such a satisfied graph. If there exists an edge between two nodes i and j, while in another graph there isn't such edge, then we regard the two graphs different.

Since the answer may be very large, please print the answer modulo 109+7.

 

 

Input

The input contains several test cases, no more than 10 test cases.

In each test case, the first line contains an integer 

n(1≤n≤50), denoting the number of nodes in the graph.

In the following n lines, every line contains a string with n characters. These strings describes the adjacency matrix of the graph. Suppose the j-th number of the i-th line is c(0≤c≤9), if c is a positive integer, there is an edge between i and j with length of c, if c=0, then there isn't any edge between i and j.

The input data ensure that the i-th number of the i-th line is always 0, and the j-th number of the i-th line is always equal to the i-th number of the j-th line.

 

 

Output

For each test case, print a single line containing a single integer, denoting the answer modulo 

109+7.

 

 

Sample Input

2 01 10 4 0123 1012 2101 3210

 

 

Sample Output

1 6

 

 

Source

 

 

Recommend

jiangzijing2015   |   We have carefully selected several similar problems for you:            

#include
       
        using namespace std;const int mod=1e9+7;string s[100];int mp[100][100],n;int dis[100],vis[100],in_[100];struct node{    int to,v;    friend bool operator < (node a,node b){
     return a.v
        
          (node a,node b){
     return a.v>b.v;};};void dij(){    priority_queue
         
          
           ,greater
           
             >q;    memset(dis,0x3f,sizeof(dis));    memset(vis,0,sizeof(vis));    dis[0]=0;vis[0]=1;q.push({
     0,0});    while(!q.empty()){        node u=q.top();q.pop();        if(u.v>dis[u.to]) continue;        for(int i=0;i
            
             dis[u.to]+mp[u.to][i]){ dis[i]=dis[u.to]+mp[u.to][i]; q.push({i,dis[i]}); } } }}int main(){ while(cin>>n){ for(int i=0;i
             
              >s[i]; memset(in_,0,sizeof(in_)); for(int i=0;i
             
            
           
          
         
        
       

#include
       
        using namespace std;const int mod=1e9+7;string s[100];int mp[100][100],n;int dis[100],vis[100],in_[100];void dij(){    //priority_queue
        
         
          ,greater
          
            >q;    queue
           
            q;    memset(dis,0x3f,sizeof(dis));    memset(vis,0,sizeof(vis));    dis[0]=0;vis[0]=1;q.push(0);    while(!q.empty()){        int u=q.front();q.pop();vis[u]=0;        for(int i=0;i
            
             dis[u]+mp[u][i]){ dis[i]=dis[u]+mp[u][i]; if(!vis[i]){ q.push(i); vis[i]=1; } } } }}int main(){ while(cin>>n){ for(int i=0;i
             
              >s[i]; memset(in_,0,sizeof(in_)); for(int i=0;i