E. Модница
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нюша — большая модница и поклонница косметики. В её коллекции сотни баночек с пудрами, помадами и кремами. Перед каждой прогулкой с Барашем она наносит макияж, чтобы подчеркнуть свою элегантность.

Как известно любой моднице, не все косметические средства хорошо сочетаются друг с другом. Чтобы навести порядок в своей огромной коллекции, Нюша расставила всю косметику в один длинный ряд. Каждой баночке $$$i$$$ она сопоставила целое число $$$a_i$$$ — числовую характеристику её стиля.

Нюша придумала особое правило для оценки сочетаемости средств: для любого набора баночек она вычисляет так называемое магическое число — наибольший общий делитель (НОД) их числовых характеристик. Для одного средства магическое число равно самому этому числу: НОД$$$(a_i)= a_i$$$.

Поскольку ряд косметики получился очень длинным, для одного макияжа Нюша решила использовать только средства, стоящие подряд, то есть некоторый подотрезок в этом ряду. Прогулок с Барашем предстоит много, и Нюша хочет каждый раз выглядеть по-новому.

Нюша хочет рассмотреть все возможные подотрезки (все способы выбрать подряд идущие баночки), вычислить магическое число для каждого из них, а затем найти сумму всех этих магических чисел. Помогите Нюше найти это итоговое число!

Так как ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$ (т.е. остаток от деления на $$$10^9+7$$$).

Входные данные

В первой строке находится одно целое число $$$n\ (1 \le n \le 200\ 000)$$$ — количество косметических средств.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числовые характеристики стиля средств.

Выходные данные

Выведите одно целое число — сумму магических чисел всех подотрезков по модулю $$$10^9 + 7$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачиИнформация о проверке
$$$1$$$$$$15$$$$$$n \le 50 $$$первая ошибка
$$$2$$$$$$35$$$$$$n \le 1000$$$$$$1$$$первая ошибка
$$$3$$$$$$20$$$$$$n \le 50\ 000$$$$$$1,2$$$первая ошибка
$$$4$$$$$$30$$$—$$$1,2,3$$$первая ошибка
Примеры
Входные данные
3
6 10 15
Выходные данные
39
Входные данные
5
12 4 8 6 1
Выходные данные
53
Примечание

Массив $$$a = [6, 10, 15]$$$. Найдём сумму наибольших общих делителей для всех подотрезков.

  • Подотрезки длины 1:
    • $$$[6]$$$ $$$\rightarrow$$$ НОД = $$$6$$$;
    • $$$[10]$$$ $$$\rightarrow$$$ НОД = $$$10$$$;
    • $$$[15]$$$ $$$\rightarrow$$$ НОД = $$$15$$$.
  • Подотрезки длины 2:
    • $$$[6, 10]$$$ $$$\rightarrow$$$ НОД$$$(6, 10) = 2$$$;
    • $$$[10, 15]$$$ $$$\rightarrow$$$ НОД$$$(10, 15) = 5$$$.
  • Подотрезки длины 3:
    • $$$[6, 10, 15]$$$ $$$\rightarrow$$$ НОД$$$(6, 10, 15) =$$$ НОД$$$(2, 15) = 1$$$.

Общая сумма: $$$6 + 10 + 15 + 2 + 5 + 1 = 39$$$.