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
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
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
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.
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
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
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$.
|Sample Input 1
||Sample Output 1
|Sample Input 2
||Sample Output 2