Classical Hard GCD Problem

$\mathbb{Mr. \ COACH}$ likes teaching his students about divisors. He came up with the following problem:

You are given an array $A$ of length $n$. We define $f(i,j) = gcd(a_i, a_{i+1}, \ldots a_j) \cdot max(a_i, a_{i+1}, \ldots a_j)$.

Determine $\sum_{i=1}^{n} \sum_{j=i}^{n}f(i,j)$ modulo $10^9 + 7$

Input data

The first line will contain $n$ ($1 \le n \le 2 \cdot 10^5$). On the next line there are $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$)

Output data

Print the sum modulo $10^9 + 7$

Example 1

stdin

4
1 2 3 4
Copy

stdout

50
Copy

Example 2

stdin

5
2 4 6 12 3
Copy

stdout

457
Copy