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 from $2$ to $10^9$ inclusive. She also gives the students crepe paper streamers. The students stretch these streamers between pairs of students and pull them tight, following these 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 two streamers may cross.
• A student may hold an end of any number of streamers.

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

If the same numbers are given in the order $3, 30, 2, 45$, there are three ways to stretch the streamers:

In how many ways can the students hold the streamers while following all of Ms. Hall's rules? Two ways are different if and only if there are two students with a streamer between them in one way and no streamer between them in the other.

The input consists of a single test case.

The first line contains an integer $n$ ($2 \le n \le 300$), the number of students.

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

Print the number of ways the students can satisfy the rules, modulo $10^9 + 7$.