Little Elephant and LCM

题意翻译

对于一个数组a,有数组b使得b[i]<=a[i]并且b中所有数的最小公倍数等于b中所有数字的最大值,求这样的数组b的个数mod1000000007.

题目描述

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) $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

4
1 4 3 2

输出样例 #1

15

输入样例 #2

2
6 3

输出样例 #2

13