L. Square
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \gt 0$$$.
  • For each $$$i~(1\le i \lt 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$$$.

Input

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

Output one integer – the answer modulo $$$1000000007$$$.

Example
Input
3
2 3 6
Output
6