GCD of Contiguous Subseqence 2

問題文

長さ$N$の数列$A$が与えられます．「数列$A$の空でない全ての連続部分列」における「連続部分列の長さ $\times$ 全要素の最大公約数」の総和を$1000000007$で割ったあまりを求めてください．つまり，

を$1000000007$で割ったあまりを求めてください．

ただし，部分列の要素が同じでも、取り出す位置が異なっていれば別の部分列として数えます．

また，数列の要素が$1$つの場合はその要素の値を最大公約数とします．つまり，任意の自然数$x$について，$\gcd(x)=x$です．

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数

入力

出力

$\displaystyle \sum_{1 \leq i \leq N} \sum_{i \leq j \leq N} ((j-i+1) \times \gcd(A_i, A_{i+1}, \dots A_{j-1},A_j))$ を$1000000007$で割ったあまりを出力してください．

サンプル

5
8 3 80 4 164

310

以下では$(j-i+1) \times \gcd(A_i, A_{i+1}, \dots A_{j-1},A_j)$ をポイントと呼びます．

• $[8]$の長さは$1$，最大公約数は$8$なのでポイントは$8$です．
• $[8,3]$の長さは$2$，最大公約数は$1$なのでポイントは$2$です．
• $[8,3,80]$の長さは$3$，最大公約数は$1$なのでポイントは$3$です．
• $[8,3,80,4]$の長さは$4$，最大公約数は$1$なのでポイントは$4$です．
• $[8,3,80,4,164]$の長さは$5$，最大公約数は$1$なのでポイントは$5$です．
• $[3]$の長さは$1$，最大公約数は$3$なのでポイントは$3$です．
• $[3,80]$の長さは$2$，最大公約数は$1$なのでポイントは$2$です．
• $[3,80,4]$の長さは$3$，最大公約数は$1$なのでポイントは$3$です．
• $[3,80,4,164]$の長さは$4$，最大公約数は$1$なのでポイントは$4$です．
• $[80]$の長さは$1$，最大公約数は$80$なのでポイントは$80$です．
• $[80,4]$の長さは$2$，最大公約数は$4$なのでポイントは$8$です．
• $[80,4,164]$の長さは$3$，最大公約数は$4$なのでポイントは$12$です．
• $[4]$の長さは$1$，最大公約数は$4$なのでポイントは$4$です．
• $[4,164]$の長さは$2$，最大公約数は$4$なのでポイントは$8$です．
• $[164]$の長さは$1$，最大公約数は$164$なのでポイントは$164$です．

これらを合計すると$310$になります．

5
12 12 12 12 6

330