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 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, …, 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≤10^5 ~).

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

Kết quả:

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

Ví dụ:

Input

5
3  2  4  3  1 

Output

36 

Ràng buộc:

• 30% test với ~ 1<N≤20;1≤Ai≤20 ~.
• 40% test với ~ 1≤N≤10^5;~ ~A_i~ là số nguyên tố nhỏ hơn ~10^6( 1≤i≤N) ~.
• 30% số test còn lại không có ràng buộc gì thêm.