그래프의 해시

해시는 주어진 데이터를 하나의 수로 나타내는 방법이다. 이 문제에서는 그래프에 대해 다음과 같이 해시 값을 정의한다.

1번 정점에서 2번 정점으로 가는 모든 단순 경로를 생각하자. 단순 경로에서는 같은 정점이 두 번 이상 등장할 수 없다. 한 경로의 값은 그 경로에 포함된 모든 간선 가중치의 최대공약수이다. 그래프의 해시 값은 이러한 모든 경로 값의 최소공배수이다.

주어진 그래프의 해시 값을 구하는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 N (2 <= N <= 30)이 주어진다.

다음 N개의 줄에는 각각 N개의 음이 아닌 정수가 주어지며, 이는 대칭인 인접 행렬을 이룬다. 값이 0이면 해당 간선이 없다는 뜻이다. 0이 아닌 간선의 가중치는 1 이상 5000 이하의 정수이다.

그래프의 해시 값을 10진수로 출력한다. 이 값은 1000자리를 넘지 않는다.