Father Study 非常热爱数学。

给定一个整数序列 $a_1, a_2, \dots, a_n$，Father Study 想要计算另一个整数序列 $t_1, t_2, \dots, 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, \dots, a_n$ ($1 \le a_i \le 1000000$)，由空格分隔。

输出格式

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

样例

输入 1

3
2 3 6

输出 1

6