C. Маленький Слоник и НОК
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Слоник любит операцию НОК (наименьшее общее кратное) непустого множества целых положительных чисел. Результат операции НОК k целых положительных чисел x1, x2, ..., xk — это минимальное целое положительное число, которое делится на каждое из чисел xi.

Пусть задана последовательность целых чисел b1, b2, ..., bn. Обозначим через lcm(b1, b2, ..., bn) их НОК, а через max(b1, b2, ..., bn) — максимальное из них. Маленький Слоник считает последовательность b хорошей, если lcm(b1, b2, ..., bn) = max(b1, b2, ..., bn).

У Маленького Слоника есть последовательность целых чисел a1, a2, ..., an. Помогите ему найти количество хороших последовательностей целых чисел b1, b2, ..., bn таких, что для всех i (1 ≤ i ≤ n) выполняется 1 ≤ bi ≤ ai. Так как ответ может быть довольно большим, выведите остаток от его деления на 1000000007 (109 + 7).

Входные данные

В первой строке записано единственное целое положительное число n (1 ≤ n ≤ 105) — количество чисел в последовательности a. Во второй строке записаны n целых чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 105) — последовательность a.

Выходные данные

В единственной строке выведите одно целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
4
1 4 3 2
Выходные данные
15
Входные данные
2
6 3
Выходные данные
13