Be Geeks!

题号：NC209400
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 ≤ i ≤ j ≤ N$ .
Let $M(i,j) = max(ai ,ai+1 ,...,aj)$ , where $1 ≤ i ≤ j ≤ N$ .
Let $P(i,j) = G(i,j) · M(i,j)$ , where $1 ≤ i ≤ j ≤ N$ .
Let $F(A)=∑P(i,j)$ over all pairs of integers $1≤i≤j≤N$ . The function 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.

输入描述:

The first line contains one integer . 
The next line contains  integers .

输出描述:

Print the value of F(A) modulo 1000000007.

示例1

输入

复制

4
1 2 3 4

输出

复制

示例2

输入

复制

5
2 4 6 12 3

输出

复制