题目描述

在顿河畔罗斯托夫的入口，矗立着著名的塔昌卡纪念碑，旁边的巨型字母拼成了这座城市的名字。每个字母都有自己的高度。当地居民热爱信息学竞赛，喜欢研究城市景观中隐藏的数列性质。

考虑一个非空的正整数序列 $A=(a_1,a_2,\dots,a_N)$，其中 $a_i$ 表示纪念碑上第 $i$ 个字母的高度。

对于任意满足 $1\le i\le j\le N$ 的下标 $i,j$，定义：

• $\operatorname{GCD}(i,j)=\gcd(a_i,a_{i+1},\dots,a_j)$；
• $\operatorname{Max}(i,j)=\max(a_i,a_{i+1},\dots,a_j)$；
• $\operatorname{Prod}(i,j)=\operatorname{GCD}(i,j)\cdot\operatorname{Max}(i,j)$。

其中，$\gcd$ 表示这些数的最大公约数。

需要计算的值为

$$F(A)=\sum_{1\le i\le j\le N}\operatorname{Prod}(i,j).$$

请计算 $F(A)$ 对 $1\,000\,000\,007$ 取模的结果。

输入格式

第一行包含一个整数 $N$（$1\le N\le2\cdot10^5$），表示字母的数量。

第二行包含 $N$ 个整数 $a_1,a_2,\dots,a_N$（$1\le a_i\le10^9$），表示各个字母的高度。

输出格式

输出一个整数，表示 $F(A)$ 对 $1\,000\,000\,007$ 取模的结果。

1
14

196

2
11 16

393

3
20 11 12

717