题目背景

题目译自 CERC 2019 「Be Geeks!」

题目描述

音乐乐队 Be Geeks! 的名字并非偶然，因为所有成员都是真正的数学怪才。除此之外，他们喜欢研究数列的各种性质。下面是他们感兴趣的一个例子：

• 设 $A$ 是一个非空正整数序列，$A=(a_1, a_2, \dots, a_N)$。
• $G(i, j)=\gcd (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。
• $M(i, j)=\max (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。
• $P(i, j)=G(i, j)\times M(i, j)$，其中 $1\le i\le j\le N$。
• $F(A)=\sum P(i, j)[1\le i\le j\le N]$。

给出一个序列 $A$，你需要求出 $F(A)\bmod 1\,000\,000\,007$ 的值。

输入格式

第一行包含一个整数 $N\ (1\le N\le 2\times 10^5)$，代表序列 $A$ 的长度。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N\ (1\le a_i\le 10^9)$，代表序列 $A$。

输出格式

输出一个整数，代表 $F(A)\bmod 1\,000\,000\,007$ 的值。

4
1 2 3 4

50

5
2 4 6 12 3

457