Cho một dãy số ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, … , 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 thỏa 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, … , 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~.

Input

Đọc từ file văn bản SCP.inp gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ (~N \le 10^5~).

• Dòng thứ hai ghi ~N~ số nguyên dương ~A_1, A_2, … , A_N~ (~0 < A_i \le 10^6~, ~1 \le i \le N~).

Output

Ghi ra file văn bản SCP.out kết quả theo yêu cầu của bài toán.

Ràng buộc

• ~1 \le N \le 10^5~
• ~0 < A_i \le 10^6~ với ~1 \le i \le N~

Sample Input

5
3 2 4 3 1

Sample Output

36