Problems
Be Geeks!
Be Geeks!
The musical band Be Geeks! got its name by no accident, as all the members are genuine math geeks. Among others, they love examining various properties of number sequences. Let’s see an example of their subject of interest.
Let $A$ be a nonempty sequence of positive integers, $A = (a_1, a_2, ..., a_n)$.
Let $G(i, j) = gcd(a_i, a_{i+1}, ..., a_j)$, where $1 \le i \le j \le n$.
Let $M(i, j) = max(a_i, a_{i+1}, ..., a_j)$, where $1 \le i \le j \le n$.
Let $P(i, j) = G(i, j) * M(i, j)$, where $1 \le i \le j \le n$.
Let $F(A) = Σ P(i, j)$ over all pairs of integers $1 \le i \le j \le n$.
The function \textbf{gcd} stands for the greatest common divisor of the given values. The greatest common divisor of a nonempty sequence of integers is the biggest integer which divides each integer in the sequence evenly.
\InputFile
The first line contains one integer $n~(1 \le n \le 2 \cdot 10^5)$.
The next line contains $n$ integers $a_1, a_2, ..., a_n~(1 \le a_i \le 10^9)$.
\OutputFile
Print the value of $F(A)$ modulo $10^9 + 7$
Input example #1
4 1 2 3 4
Output example #1
50
Input example #2
5 2 4 6 12 3
Output example #2
457