平方

【题目背景】

平时多积淀，战时方致远。

【题目描述】

给定一个长度为 $n$ 的序列 $a_1，a_2, \cdots ,a_n$;

求出另一个长度为 $n$ 的序列 $b_1，b_2, \cdots ,b_n$，满足：

$\bullet$ $\forall i | 1 \leq i \leq n,b_i \gt 0$;

$\bullet$ $\forall i | 1 \leq i \leq n,a_i \times a_{i+1} \times b_i \times b_{i+1} $是完全平方数;

$\bullet$ $\prod_{i=1}^{n} b_i$ 尽可能小。

请你帮忙计算 $\prod_{i=1}^{n} b_i$ 对 $10,0000,0007$ 取模后的结果。

【输入格式】

第一行一个整数 $n$，表示序列长度。

接下来一行包含 $n$ 个整数 $a_i$。

【输出格式】

输出共一行，表示符合 题意的最小值对 $10,0000,0007$ 取模后的结果。

【样例输入1】

3
2 3 6

【样例输出1】

6

【样例输入2】

5
1 2 2 1 2

【样例输出2】

4

【样例输入3】

5
1 2 3 4 8

【样例输出3】

12

【样例4】

点击下载样例2

【数据规模与约定】

测试点 $1：n=2$;

测试点 $2：n=10$;

测试点 $3：a_i \leq 2$;

测试点 $4,5,6：a_i \leq 100$;

测试点 $7,8,9,10：$无额外限制;

对于所有测试点，满足：$n \leq 10^5，1 \leq a_i \leq 10^6$。