P9607 [CERC2019] Be Geeks!

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[Be Geeks!](https://contest.felk.cvut.cz/19cerc/solved/begeeks.pdf)”.**

The music band Be Geeks! did not get its name by accident, because all members are true math geeks. Besides that, they like to study various properties of sequences. Here is an example they are interested in: - Let $A$ be a non-empty sequence of positive integers, $A=(a_1, a_2, \dots, a_N)$. - $G(i, j)=\gcd (a_i, a_{i+1}, \dots, a_j)$, where $1\le i\le j\le N$. - $M(i, j)=\max (a_i, a_{i+1}, \dots, a_j)$, where $1\le i\le j\le N$. - $P(i, j)=G(i, j)\times M(i, j)$, where $1\le i\le j\le N$. - $F(A)=\sum P(i, j)[1\le i\le j\le N]$. Given a sequence $A$, you need to compute $F(A)\bmod 1\,000\,000\,007$.

The first line contains an integer $N\ (1\le N\le 2\times 10^5)$, which is the length of sequence $A$. The second line contains $N$ integers $a_1, a_2, \dots, a_N\ (1\le a_i\le 10^9)$, representing the sequence $A$.

Output one integer, which is the value of $F(A)\bmod 1\,000\,000\,007$.

Translated by ChatGPT 5