P10827 [EC Final 2020] Square

Father Study loves math very much. Given a sequence of integers $a_1,a_2,...,a_n$, Father Study wants to calculate another sequence of integers $t_1,t_2,...,t_n$ satisifing - For each $i~(1 \le i \le n)$, $t_i > 0$. - For each $i~(1\le i < n)$, $a_i \times t_i \times a_{i+1} \times t_{i+1}$ is a square number. (In mathematics, a square number or perfect square is an integer that is the square of an integer, in other words, it is the product of some integer with itself.) - $\prod_{i=1}^{n}{t_i}$ is minimized. Please help Father Study to calculate the answer --- the minimum value of $\prod_{i=1}^{n}{t_i}$. Because the answer is too large, please output the answer modulo $1000000007$.

The first line contains a single integer $n$ ($1\le n \le 100000$). The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \le a_i \le 1000000$) separated by single spaces.

Output one integer -- the answer modulo $1000000007$.