Chú voi con và LCM

Cho dãy số nguyên dương $a_1,a_2,\dots ,a_n$.

Xét một dãy số nguyên dương $b_1,b_2,\dots ,b_n$. Gọi $\text{lcm}(b_1,\dots ,b_n)$ là bội chung nhỏ nhất và $max(b_1,\dots ,b_n)$ là giá trị lớn nhất của dãy $b$. Dãy $b$ được gọi là tốt nếu:

$$\text{lcm}(b_1,b_2,\dots ,b_n)=max(b_1,b_2,\dots ,b_n).$$

Hãy đếm số dãy tốt $b_1,b_2,\dots ,b_n$ thoả mãn $1\le b_i\le a_i$ với mọi $i$ ($1\le i\le n$). Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương $n$: số phần tử của dãy $a$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: số dãy tốt theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^5$

Ví dụ