Cho dãy số nguyên dương ~A_1, A_2, \dots, A_n~.

Yêu cầu

Hãy tính số nguyên dương nhỏ nhất chia hết cho tất cả các phần tử của dãy, tức là giá trị

~\operatorname{lcm}(A_1, A_2, \dots, A_n)~.

Vì kết quả có thể rất lớn, chỉ cần in ra kết quả theo modulo ~10^9 + 7~.

Dữ liệu

Dòng đầu tiên chứa một số nguyên ~n~.

Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, \dots, A_n~.

Kết quả

In ra một số nguyên duy nhất là

~\operatorname{lcm}(A_1, A_2, \dots, A_n) \bmod (10^9 + 7)~.

Ví dụ

Ví dụ 1

Input

4
1 3 4 5

Output

60

Giải thích

Ví dụ 1

Ta có ~\operatorname{lcm}(1, 3, 4, 5) = 60~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n \le 10^5~

~1 \le A_i \le 10^5~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~1 \le n \le 10~, ~1 \le A_i \le 10^2~.
• Subtask ~2~ ~(40\%):~ ~1 \le n \le 10^3~, ~1 \le A_i \le 10^3~.
• Subtask ~3~ ~(40\%):~ Không có ràng buộc bổ sung.