(scp.*)

Cho một dãy số A gồm \(N\) số nguyên dương \(A_{1},\ A_{2},\ \ldots,\ A_{N}\). Một số nguyên dương \(K\) được gọi là số siêu chính phương của dãy \(A\) nếu thoả mãn đồng thời hai điều kiện:

- Số \(K\) là một số chính phương.

- Số \(K\) chia hết cho tất cả các phần tử \(A_{1},\ A_{2},\ \ldots,\ A_{N}.\)

Yêu cầu: Hãy lập trình tìm số siêu chính phương \(K\) nhỏ nhất của dãy A. Do số \(K\) có thể rất lớn nên bạn chỉ cần đưa ra kết quả là số dư của phép chia \(K\) cho \(1000000007.\)

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(N\) (\(N \leq 10^{5}\)).

- Dòng thứ hai ghi \(N\) số nguyên dương\(\ A_{1},\ A_{2},\ \ldots,A_{N}\) \((0 < A_{i} \leq 10^{6},\ 1 \leq i \leq N)\).

Dữ liệu ra:

+ Ghi một số nguyên cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- 30% test với \(1 < N \leq 20;1 \leq A_{i} \leq 20\).

- 40% test với \(1 \leq N \leq 10^{5};\ A_{i}\ là\ số\ nguyên\ tố\ nhỏ\ hơn\ 10^{6}(\ 1 \leq i \leq N)\).

- 30% số test còn lại không có ràng buộc gì thêm.