小象喜欢非空正整数集的 LCM(最小公倍数)运算。 k个正整数x1,x2,...,xk的最小公倍数运算的结果是能被每个数字xi整除的最小正整数。
假设有一个整数序列 b1, b2, ..., bn。我们将它们的 LCM 表示为 lcm(b1, b2, ..., bn),将它们的最大值表示为 max(b1, b2, ..., bn)。如果 lcm(b1, b2, ..., bn) = max(b1, b2, ..., bn),小象认为序列 b 是好的。
小象有一个整数序列 a1, a2, ..., an。帮助他找到整数 b1, b2, ..., bn 的良好序列的数量,使得对于所有 i (1 ≤ i ≤ n) 满足以下条件:1 ≤ bi ≤ ai。由于答案可能相当大,因此打印除以 1000000007 (109 + 7) 所得的余数。
输入
第一行包含一个正整数 n (1 ≤ n ≤ 105) — 序列 a 中整数的数量。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 105) — 序列 a。
输出
在单行中打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
4 1 4 3 2
输出 #1
15
输入 #2
2 6 3
输出 #2
13