Description

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$ 取模的结果。

Input Format

第一行包含一个整数 $n$ ($1\le n \le 100000$)。

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

Output Format

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

3
2 3 6

6

Hint

（由 ChatGPT 4o 翻译）