P10827 [EC Final 2020] Square

Father Study 非常喜欢数学。 给定一个整数序列 $a_1,a_2,...,a_n$，Father Study 想要计算另一个整数序列 $t_1,t_2,...,t_n$，满足以下条件： - 对于每个 $i~(1 \le i \le n)$，有 $t_i > 0$。 - 对于每个 $i~(1\le i < n)$，$a_i \times t_i \times a_{i+1} \times t_{i+1}$ 是一个完全平方数。（在数学中，完全平方数是一个整数，它是某个整数的平方，换句话说，它是某个整数与其自身的乘积。） - $\prod_{i=1}^{n}{t_i}$ 的值最小。 请帮助 Father Study 计算答案，即 $\prod_{i=1}^{n}{t_i}$ 的最小值。由于答案可能过大，请输出答案对 $1000000007$ 取模的结果。

第一行包含一个整数 $n$ ($1\le n \le 100000$)。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 \le a_i \le 1000000$)，它们由单个空格分隔。

输出一个整数，即答案对 $1000000007$ 取模的结果。

（由 ChatGPT 4o 翻译）