Square

Father Study loves math very much.

Given a sequence of integers $a_1, a_2, \ldots, a_n$, Father Study wants to calculate another sequence of integers $t_1, t_2, \ldots, t_n$ that satisfies the following conditions.

• 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.

Find the minimum value of $\prod_{i=1}^{n}{t_i}$.

The first line contains a single integer $n$ ($1 \le n \le 100000$).

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

Output one integer, the minimum value of $\prod_{i=1}^{n}{t_i}$ modulo $1000000007$.