A. Another Problem About Maximum in Range
time limit per test
2 с
memory limit per test
256 МБ
input
standard input
output
standard output

Given a sequence of integers $$$a_1, a_2, \dots, a_N$$$, find:

$$$$$$\left( \sum\limits_{i=1}^N \sum\limits_{j=i}^N \max(a_i, a_{i+1}, \cdots, a_j) \times \gcd(i, j)^2 \right) \pmod{10^9 + 7}$$$$$$

where $$$\gcd$$$ is the greatest common divisor function.

Input

The first line of input contains an integer $$$N \left( 1 \le N \le 5\times 10^5 \right)$$$, indicating the size of the sequence.

The second line contains $$$N$$$ positive integers, $$$a_i \left( 1 \le a_i \le 10^9 \right)$$$, separated by spaces, representing the sequence of numbers.

Output

On a single line print the answer to the problem.

Example
Input
3
1 2 3
Output
44
Note

In the example, we have the sequence 1, 2, 3 with the following ranges:

  1. $$$[1, 1], [2, 2], [3, 3]$$$ whose maxima are $$$\max(a[1, 1]) = 1$$$, $$$\max(a[2, 2]) = 2$$$, $$$\max(a[3, 3]) = 3$$$
  2. $$$[1, 2], [2, 3]$$$ whose maxima are $$$\max(a[1, 2]) = 2$$$, $$$\max(a[2, 3]) = 3$$$
  3. $$$[1, 3]$$$ whose maximum is $$$\max(a[1, 3]) = 3$$$

Thus, the sum is developed as $$$$$$ \max(a[1, 1]) \cdot \gcd(1, 1)^2 + \max(a[2, 2]) \cdot \gcd(2, 2)^2 + \max(a[3, 3]) \cdot \gcd(3, 3)^2 \\ + \max(a[1, 2]) \cdot \gcd(1, 2)^2 + \max(a[2, 3]) \cdot \gcd(2, 3)^2 + \max(a[1, 3]) \cdot \gcd(1, 3)^2. $$$$$$

Replacing the values, we get $$$$$$ 1 \cdot \gcd(1, 1)^2 + 2 \cdot \gcd(2, 2)^2 + 3 \cdot \gcd(3, 3)^2 \\ + 2 \cdot \gcd(1, 2)^2 + 3 \cdot \gcd(2, 3)^2 + 3 \cdot \gcd(1, 3)^2. $$$$$$

and then $$$$$$ 1 \cdot 1^2 + 2 \cdot 2^2 + 3 \cdot 3^2 + 2 \cdot 1^2 + 3 \cdot 1^2 + 3 \cdot 1^2 \\ = 1 + 8 + 27 + 2 + 3 + 3 = 44. $$$$$$

Finally, taking this result modulo $$$10^9 + 7$$$, we still get $$$44$$$ since $$$44 \lt 10^9 + 7$$$.