408258: GYM103069 L 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$$$.

3
2 3 6

6