제곱수

Father Study는 수학을 매우 좋아한다.

정수 수열 $a_1, a_2, \ldots, a_n$이 주어진다. Father Study는 다음 조건을 만족하는 정수 수열 $t_1, t_2, \ldots, t_n$을 구하려 한다.

• 모든 $i (1 \le i \le n)$에 대해 $t_i > 0$이다.
• 모든 $i (1 \le i < n)$에 대해 $a_i \times t_i \times a_{i+1} \times t_{i+1}$이 제곱수이다. (수학에서 제곱수는 어떤 정수의 제곱, 즉 어떤 정수에 자기 자신을 곱한 수이다.)
• $\prod_{i=1}^{n}{t_i}$가 최소가 되어야 한다.

$\prod_{i=1}^{n}{t_i}$의 최솟값을 구한다.

첫째 줄에 정수 $n$ ($1 \le n \le 100000$)이 주어진다.

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1000000$)이 공백으로 구분되어 주어진다.

$\prod_{i=1}^{n}{t_i}$의 최솟값을 $1000000007$로 나눈 나머지를 한 줄에 출력한다.