Be Geeks!
Be Geeks!
Музыкальная группа 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.
Функция НОД обозначает наибольший общий делитель.
Входные данные
Первая строка содержит одно целое число n~(1 \le n \le 2 \cdot 10^5).
Следующая строка содержит n целых чисел a_1, a_2, ..., a_n~(1 \le a_i \le 10^9).
Выходные данные
Выведите значение F(A) по модулю 10^9 + 7.
Пример
4 1 2 3 4
50
5 2 4 6 12 3
457