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$ $(10^{9} + 7)$.

Input

The first line contains a single positive integer $*n*$ $(1 ≤ *n* ≤ 10^{5})$ — 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*} ≤ 10^{5})$ — sequence $*a*$.

Output

In the single line print a single integer — the answer to the problem modulo $1000000007$ $(10^{9} + 7)$.