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