Background

This problem is translated from CERC 2019 “Be Geeks!”.

Problem Description

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$.

Input Format

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 Format

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

4
1 2 3 4

50

5
2 4 6 12 3

457

Hint

Translated by ChatGPT 5