J. JSUM
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
thy problem is mine but one letter is hath changed
— Juan, Juan Words to Ahmad

Juan stayed up late thinking of how to steal Ahmad's problem, and he figured if he just changed one character no one will know.

You are given an array $$$a$$$ of $$$n$$$ integers.

Let's define a function $$$JCD(l, r)$$$ as the greatest common divisor of the sub array $$$(a_l, .., a_r)$$$, i.e $$$GCD(a_l, a_{l + 1}, ..., a_r)$$$.

Calculate $$${\sum_{l = 1}^n {\sum_{r = l}^n JCD(l, r)}}$$$, since the answer can be very large output it modulo $$$10^9 + 7$$$.

Input

The first line contains one integer $$$N$$$ $$$(n \leq 10^5)$$$ – the size of the array.

The second line contains $$$N$$$ integers $$$(1 \leq a_i \leq 10^{12})$$$.

Output

Output the answer to the problem modulo $$$10^9 + 7$$$.

Examples
Input
3
1 2 3
Output
9
Input
9
8 4 16 2 1 3 5 7 49
Output
149
Input
4
3 7 14 8
Output
45