Музыкальная группа Be Geeks! получила свое название не случайно, так как все ее участники --- настоящие математики. Среди прочего, они любят изучать различные свойства числовых последовательностей. Давайте посмотрим на интересующую их тему. Пусть $A$ --- непустая последовательность натуральных чисел, $A = (a_1, a_2, ..., a_n)$. Пусть $G(i, j) = НОД(a_i, a_{i+1}, ..., a_j)$, где $1 \le i \le j \le n$. Пусть $M(i, j) = max(a_i, a_{i+1}, ..., a_j)$, где $1 \le i \le j \le n$. Пусть $P(i, j) = G(i, j) * M(i, j)$, где $1 \le i \le j \le n$. Пусть $F(A) = Σ P(i, j)$ по всем парам целых чисел $1 \le i \le j \le n$. Функция \textbf{НОД} обозначает наибольший общий делитель. \InputFile Первая строка содержит одно целое число $n~(1 \le n \le 2 \cdot 10^5)$. Следующая строка содержит $n$ целых чисел $a_1, a_2, ..., a_n~(1 \le a_i \le 10^9)$. \OutputFile Выведите значение $F(A)$ по модулю $10^9 + 7$.