Ms. Hall 想要教她的学生关于公因数的知识。她将学生排成一个圆圈，并为每位学生分配一个范围在 $2 \dots 10^9$（含）之间的整数。她还为学生提供了绉纸彩带。学生们需要将这些彩带拉紧并连接在两名学生之间。但是，有一些规则：

• 两名学生之间可以拉一条彩带，当且仅当他们分配到的整数拥有大于 1 的公因数。
• 圆圈中任意两名学生之间，通过彩带连接的路径有且仅有一条。
• 彩带不得交叉。
• 任何一名学生都可以握住任意多条彩带的末端。

假设 Ms. Hall 有四名学生，她给出的数字分别是 2、3、30 和 45。在这种排列下，拉彩带有一种方式：

在这种排列下，拉彩带的方式有三种：

学生们按照 Ms. Hall 的规则拉彩带，一共有多少种方式？两种方式不同，当且仅当在一种方式中两名特定学生之间有彩带，而在另一种方式中这两名学生之间没有彩带。

输入格式

输入包含一组测试用例。第一行包含一个整数 $n$ ($2 \le n \le 300$)，表示 Ms. Hall 的学生人数。

接下来的 $n$ 行，每行包含一个整数 $x$ ($2 \le x \le 10^9$)。这些数字按顺序代表学生持有的数字。请记住，学生们站成一个圆圈，因此最后一名学生与第一名学生相邻。

输出格式

输出一个整数，表示 Ms. Hall 的学生满足规则的方式总数。由于该数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

4
30
3
2
45

样例输出 1

1

样例输入 2

4
3
30
2
45

样例输出 2

3