题目描述

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