eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Be Geeks!

Be Geeks!

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Музыкальная группа 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.

Пример

Входные данные #1
4
1 2 3 4
Выходные данные #1
50
Входные данные #2
5
2 4 6 12 3
Выходные данные #2
457
Источник 2019 ACM Central Europe (CERC), Прага, Ноябрь 29 - Декабрь 1, Задача B