Chính phương

Cho một dãy số \(a\) gồm \(N\) số nguyên dương \(a_1, a_2, \dots, 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:

• \(K\) là một số chính phương;
• \(K\) chia hết cho tất cả các phần tử \(a_1, a_2, \dots, a_N\).

Yêu cầu. Hãy tìm số siêu chính phương nhỏ nhất \(K\) của dãy \(a\).
Do \(K\) có thể rất lớn, chỉ cần in ra \(K \bmod 1000000007\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((1 \le N \le 10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((1 \le a_i \le 10^6)\).

Output

• In ra một số nguyên là \(K \bmod 1000000007\).

Input

%
5
3 2 4 3 1

Output

%
36

Notes

Trong ví dụ,
số chính phương nhỏ nhất chia hết cho các phần tử của dãy \(a\) là \(36\), do đó đáp án là \(36\).

Scoring

• (50%) \(1 < N \le 20\), \(1 \le a_i \le 20\);
• (30%) \(1 \le N \le 10^5\), mọi \(a_i\) là số nguyên tố nhỏ hơn \(10^6\);
• (20%) Không có ràng buộc thêm.