Problem C
Stretching Streamers

Ms. Hall wants to teach her class about common factors. She arranges her students in a circle and assigns each student an integer in the range $[2,10^9]$. She also provides the students with crepe paper streamers. The students are to stretch these streamers between pairs of students, and pull them tight. But, there are some rules.

• Two students can stretch a streamer between them if and only if their assigned integers share a factor other than $1$.

• There is exactly one path, going from streamer to streamer, between any two students in the circle.

• No streamers may cross.

• Any given student may hold an end of arbitrarily many streamers.

Suppose Ms. Hall has four students, and she gives them the numbers $2$, $3$, $30$ and $45$. In this arrangement, there is one way to stretch the streamers:

In this arrangement, there are three ways to stretch the streamers:

In how many ways can the students hold the streamers subject to Ms. Hall’s rules? Two ways are different if and only if there is a streamer between two given students one way, but none between those two students the other way.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($2 \le n \le 300$), which is the number of Ms. Hall’s students.

Each of the next $n$ lines will hold an integer $x$ ($2 \le x \le 10^9$). These are the numbers held by the students, in order. Remember, the students are standing in a circle, so the last student is adjacent to the first student.

Output

Output a single integer, which is the number of ways Ms. Hall’s students can satisfy her rules. Since this number may be very large, output it modulo $10^9+7$.

4
30
3
2
45

1

4
3
30
2
45

3