题目描述

霍尔女士想教她的班级关于公因数的知识。她让学生们围成一个圆圈，并为每个学生分配一个 $2$ 到 $10^9$ 之间的整数。她还给学生们提供了一些皱纹纸彩带。学生们需要将这些彩带拉伸在学生之间，并拉紧。但是，必须遵守以下规则。

• 两个学生之间可以拉伸彩带当且仅当他们被分配的整数有一个大于 $1$ 的公因数。
• 在圆圈中的任意两个学生之间，恰好存在一条由彩带构成的路径。
• 彩带之间不能交叉。
• 任意学生可以握住任意多条彩带的一端。

假设霍尔女士有四个学生，她给他们分配的数字是 $2$、$3$、$30$ 和 $45$。在这种安排下，只有一种方式拉伸彩带：

:::align{center} :::

而在另一种安排下，有三种方式拉伸彩带：

:::align{center} :::

在满足霍尔女士规则的条件下，学生们有多少种握持彩带的方式？如果一种方式中某两个学生之间有彩带，而另一种方式中没有，则认为这两种方式不同。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$2 \leq n \leq 300$），表示霍尔女士的学生人数。

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

输出格式

输出一个整数，表示霍尔女士的学生们满足她规则的方式总数。由于这个数字可能非常大，请输出它对 $10^9 + 7$ 取模的结果。

4
30
3
2
45

1

4
3
30
2
45

3

提示

翻译由 DeepSeek V3.2 完成