CF258C.Little Elephant and LCM

The Little Elephant loves the LCM (least common multiple) operation of a non-empty set of positive integers. The result of the LCM operation of k positive integers _x_1, _x_2, ..., x__k is the minimum positive integer that is divisible by each of numbers x__i.

Let's assume that there is a sequence of integers _b_1, _b_2, ..., b__n. Let's denote their LCMs as lcm(_b_1, _b_2, ..., b__n) and the maximum of them as max(_b_1, _b_2, ..., b__n). The Little Elephant considers a sequence b good, if lcm(_b_1, _b_2, ..., b__n) = max(_b_1, _b_2, ..., b__n).

The Little Elephant has a sequence of integers _a_1, _a_2, ..., a__n. Help him find the number of good sequences of integers _b_1, _b_2, ..., b__n, such that for all i (1 ≤ i ≤ n) the following condition fulfills: 1 ≤ b__i ≤ a__i. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

小象热爱非空正整数集合的最小公倍数（LCM）运算。$k$ 个正整数 $x_1,\,x_2,\,\dots,\,x_k$ 的 LCM 是能被每个 $x_i$ 整除的最小正整数。

假设存在一个整数序列 $b_1,\,b_2,\,\dots,\,b_n$。记其最小公倍数为 $\mathrm{lcm}(b_1,\,b_2,\,\dots,\,b_n)$，记其最大值为 $\max(b_1,\,b_2,\,\dots,\,b_n)$。若满足 $\mathrm{lcm}(b_1,\,b_2,\,\dots,\,b_n) = \max(b_1,\,b_2,\,\dots,\,b_n)$，则小象称该序列 $b$ 是“好”的。

小象有一个整数序列 $a_1,\,a_2,\,\dots,\,a_n$。请帮助他计算满足如下条件的“好”序列 $b_1,\,b_2,\,\dots,\,b_n$ 的个数：对所有 $i$（$1\le i\le n$），均有 $1\le b_i\le a_i$。由于答案可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains a single positive integer n (1 ≤ n ≤ 105) — the number of integers in the sequence a. The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105) — sequence a.

第一行包含一个正整数 $n$（$1 \leq n \leq 10^5$）——序列 $a$ 中整数的个数。
第二行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^5$）——序列 $a$。

In the single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

在单行中输出一个整数——该问题答案对 $1000000007$（即 $10^9 + 7$）取模的结果。