Маленький Слоник любит операцию НОК (наименьшее общее кратное) непустого множества целых положительных чисел. Результат операции НОК 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).