Chỉ còn vài ngày nữa thôi là đến ngày Phụ Nữ Việt Nam 20/10 rồi, người bố bèn hẹn \(n\) người con của mình tổ chức một bữa tiệc nhỏ ở nhà cho người mẹ.

Ta sẽ đánh số các ngày như sau, hôm nay là ngày \(0\), ngày mai là ngày \(1\), ..., sau ngày \(x\) đến ngày \(x+1\) (với mọi \(x > 0\)).

Các người con được đánh số từ \(1\) đến \(n\). Tại ngày \(0\) tất cả \(n\) người con đều đang bận, người con thứ \(i\) \((1 \leq i \leq n)\) sẽ rảnh tại các ngày được đánh số \(a_i\), \(2a_i\), \(3a_i\), \(\ldots\) Các ngày còn lại người con thứ \(i\) đều bận tất.

Tức là người con thứ \(i\) sẽ chỉ rảnh tại các ngày \(k \times a_i\) \((k > 0)\) là các bội khác \(0\) của \(a_i\).

Người bố hiểu rằng nếu khi tổ chức bữa tiệc tại ngày \(x\) \((x \geq 0)\) nào đó mà chỉ cần có một người con vắng mặt (không đến được vì ngày đó bận) thì người mẹ sẽ không vui. Người bố cần tìm ngày được đánh số \(F\) \((F \geq 0)\) là ngày được đánh số nhỏ nhất và tất cả các người con đều rảnh để tổ chức bữa tiệc.

Yêu cầu: Vì \(F\) có thể rất lớn nên chỉ cần đưa ra \(F \; \% \; ({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq {10}^5)\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq {10}^6)\).

Output

• Gồm một số nguyên duy nhất là kết quả cần tìm.

Example

1
10

10

5
2 3 5 7 11

2310

4
2 14 12 10

420

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \leq 20\).
• Subtask 2 (\(25\%\) số điểm): \(n \leq 200\).
• Subtask 3 (\(25\%\) số điểm): \(n \leq 3000\).
• Subtask 4 (\(25\%\) số điểm): \(n \leq {10}^5\).