Музыкальная группа Be Geeks! получила свое название не случайно, так как все ее участники — настоящие математики. Среди прочего, они любят изучать различные свойства числовых последовательностей. Давайте посмотрим на интересующую их тему.
Пусть A — непустая последовательность натуральных чисел, A=(a1,a2,...,an).
Пусть G(i,j)=НОД(ai,ai+1,...,aj), где 1≤i≤j≤n.
Пусть M(i,j)=max(ai,ai+1,...,aj), где 1≤i≤j≤n.
Пусть P(i,j)=G(i,j)∗M(i,j), где 1≤i≤j≤n.
Пусть F(A)=ΣP(i,j) по всем парам целых чисел 1≤i≤j≤n.
Функция НОД обозначает наибольший общий делитель.
Первая строка содержит одно целое число n (1≤n≤2⋅105).
Следующая строка содержит n целых чисел a1,a2,...,an (1≤ai≤109).
Выведите значение F(A) по модулю 109+7.