종이 테이프 잇기

홀 선생님은 반 학생들에게 공약수를 가르치려고 한다. 선생님은 학생들을 원형으로 세우고 각 학생에게 $2$ 이상 $10^9$ 이하의 정수를 하나씩 나누어 준다. 그리고 학생들에게 크레이프 종이 테이프를 준다. 학생들은 두 학생 사이에 테이프를 걸고 팽팽하게 당겨야 하는데, 다음 규칙을 지켜야 한다.

• 두 학생이 받은 정수에 $1$이 아닌 공약수가 있을 때, 그리고 그때에만 두 학생 사이에 테이프를 걸 수 있다.
• 원 위의 어떤 두 학생 사이에도 테이프를 따라 이동하는 경로가 정확히 하나 있어야 한다.
• 두 테이프가 서로 교차해서는 안 된다.
• 한 학생은 테이프의 끝을 몇 개든 잡을 수 있다.

예를 들어 학생이 네 명이고 원을 따라 차례로 $30, 3, 2, 45$를 받았다면 테이프를 거는 방법은 한 가지뿐이다.

같은 수를 $3, 30, 2, 45$ 순서로 받았다면 테이프를 거는 방법은 세 가지다.

선생님의 규칙을 모두 지키면서 테이프를 거는 방법의 수를 구하시오. 어떤 두 학생 사이에 한 방법에서는 테이프가 있고 다른 방법에서는 없을 때, 그리고 그때에만 두 방법이 다르다고 한다.

입력은 하나의 테스트 케이스로 이루어진다.

첫째 줄에 학생 수 $n$ ($2 \le n \le 300$)이 주어진다.

다음 $n$개의 줄에 걸쳐 학생들이 받은 정수 $x$ ($2 \le x \le 10^9$)가 원을 따라 차례로 하나씩 주어진다. 학생들은 원형으로 서 있으므로 마지막 학생은 첫 번째 학생과 이웃한다.

규칙을 지키며 테이프를 거는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.