数列计算

题目描述

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

• 设$A$是一个非空正整数序列，$A=(a_{1},a_{2},\ldots,a_{n})$。
• $G(i,j)=\gcd(a_{i},a_{i+1},\ldots,a_{j})$，其中$1 \leq i \leq j \leq n$。
• $M(i,j)=\max(a_{i},a_{i+1},\ldots,a_{j})$，其中$1 \leq i \leq j \leq n$。
• $P(i,j)=G(i,j) \times M(i,j)$，其中$1 \leq i \leq j \leq n$。
• $F(A)=\sum P(i,j)[1 \leq i \leq j \leq n]$。

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

输入格式

第一行包含一个整数$n$，代表序列$A$的长度。

第二行包含$n$个整数$a_{1}$,$a_{2}$,$\ldots$,$a_{n}$，代表序列$A$。

输出格式

输出一个整数，代表$F(A) \bmod 1000000007$的值。

数据范围与提示

• 对于$30\%$的数据，$1 \leq n \leq 1000$；
• 对于$100\%$的数据，$1 \leq n \leq 200000$，$1 \leq a_{i} \leq 10^{9}$。

样例

4
1 2 3 4

50

5
2 4 6 12 3

457

见array3.in

见array3.out