Nam là một học sinh rất thích toán và lập trình. Một ngày nọ, trong giờ học Tin học, thầy giáo giao cho Nam một bài toán thú vị liên quan đến các thừa số nguyên tố. Thầy cho Nam một dãy số ~A~ gồm ~N~ số nguyên dương và yêu cầu Nam tìm số lớn nhất ~X~ có thể tạo ra bằng cách sau:

• Với mỗi số trong dãy ~A~, Nam cần phân tích nó thành các thừa số nguyên tố (tức là các số nguyên tố nhân với nhau để tạo thành số đó).
• Sau đó, với mỗi số nguyên tố ~p~, Nam sẽ tìm số mũ lớn nhất của ~p~ xuất hiện trong tất cả các phân tích của các số trong dãy ~A~.
• Cuối cùng, Nam tạo số ~X~ bằng cách nhân tất cả các ~p^{số mũ lớn nhất}~ lại với nhau.

Vì ~X~ có thể rất lớn, thầy yêu cầu Nam chỉ cần in ra giá trị của ~X \pmod{10^9 + 7}~. Nam rất hào hứng và muốn giải bài toán này. Bạn hãy giúp Nam lập trình.

Yêu cầu: Hãy tìm số ~X~ theo cách trên và in ra giá trị ~X \pmod{10^9 + 7}~.

Input

• Dòng 1: Chứa số nguyên ~N~ (~1 \le N \le 10^5~), là số lượng số trong dãy.
• Dòng 2: Chứa ~N~ số nguyên ~A[1], A[2], \dots, A[N]~ (~1 \le A[i] \le 10^5~), là các số trong dãy.

Output

• Ghi ra một số nguyên duy nhất, là giá trị của ~X \pmod{10^9 + 7}~.

Sample Input 1

5
4 6 8 9 15

Sample Output 1

360