Be Geeks!#9760
Sign in

Be Geeks!

1 second
128 megabytes
Very hard

The musical band Be Geeks! was aptly named, as all its members are genuine math geeks. Among other things, they enjoy exploring various properties of integer sequences. Let us take a look at one of the topics that has caught their interest.

Let be a nonempty sequence of positive integers: A = (a_1, a_2, \ldots, a_n).

For any pair of indices 1 \le i \le j \le n, define:

G(i,j) = \gcd(a_i, a_{i+1}, \ldots, a_j), \\ M(i,j) = \max(a_i, a_{i+1}, \ldots, a_j), \\ P(i,j) = G(i,j) \cdot M(i,j)

Finally, define as the sum of P(i,j) over all pairs of indices 1 \le i \le j \le n:

F(A) = \sum_{1 \le i \le j \le n} P(i,j)

Here, denotes the greatest common divisor of the given integers.

Input

The first line contains one integer n~(1 \le n \le 2 \cdot 10^5).

The second line contains integers a_1, a_2, \ldots, a_n~(1 \le a_i \le 10^9).

Output

Print the value of modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading