乐团 "Be Geeks!" 的名字绝非偶然，因为所有的成员都是真正的数学极客。在众多爱好中，他们特别喜欢研究数列的各种性质。让我们来看看他们感兴趣的一个例子。

设 $A$ 为一个由正整数组成的非空序列，$A = (a_1, a_2, \dots, a_N)$。

设 $G(i, j) = \gcd(a_i, a_{i+1}, \dots, a_j)$，其中 $1 \le i \le j \le N$。

设 $M(i, j) = \max(a_i, a_{i+1}, \dots, a_j)$，其中 $1 \le i \le j \le N$。

设 $P(i, j) = G(i, j) \cdot M(i, j)$，其中 $1 \le i \le j \le N$。

设 $F(A) = \sum P(i, j)$，对所有满足 $1 \le i \le j \le N$ 的整数对求和。

函数 $\gcd$ 表示给定数值的最大公约数。一个非空整数序列的最大公约数是能够整除该序列中每个整数的最大整数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 2 \cdot 10^5$)。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$)。

输出格式

输出 $F(A)$ 模 $1\,000\,000\,007$ 的值。

样例

输入样例 1

4
1 2 3 4

输出样例 1

50

输入样例 2

5
2 4 6 12 3

输出样例 2

457