31088번 - 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ドル$.

제한

힌트