Graph Hash

A hash maps given data to a single number. For a graph, define the hash value as follows.

Consider every simple path from vertex 1 to vertex 2. The value of one path is the greatest common divisor of all edge weights on that path. The hash value of the graph is the least common multiple of the values of all such paths.

Write a program that computes this hash value for the given graph.

The first line contains the number of vertices N (2 <= N <= 30).

Each of the next N lines contains N nonnegative integers, forming a symmetric adjacency matrix. A value of 0 means that there is no edge. Every nonzero edge weight is an integer from 1 to 5000.

Print the graph hash value in decimal notation. The value has at most 1000 decimal digits.