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

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

У Маленького Слоника есть последовательность целых чисел a₁, a₂, ..., a_n. Помогите ему найти количество хороших последовательностей целых чисел b₁, b₂, ..., b_n таких, что для всех i (1 ≤ i ≤ n) выполняется 1 ≤ b_i ≤ a_i. Так как ответ может быть довольно большим, выведите остаток от его деления на 1000000007 (10⁹ + 7).