Cho trước \(A\) là một dãy số nguyên dương có ít nhất một phần tử, \(A=(a_1,a_2,...,a_N)\).

Đặt \(G(i,j)=gcd(a_i,a_{i+1},...,a_j)\) với \(1\leq i\leq j\leq N\).

Đặt \(M(i,j)=max(a_i,a_{i+1},...,a_j)\) với \(1\leq i\leq j\leq N\).

Đặt \(P(i,j)=G(i,j)∗M(i,j)\) với \(1\leq i\leq j\leq N\).

Đặt \(F(A)=∑P(i,j)\) với tất cả các cặp \(1\leq i\leq j\leq N\).

Ghi chú

\(gcd(a,b,c,d,...)\) trả về ước số chung lớn nhất của các giá trị \(a, b, c, d,\) etc.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1\leq N\leq 2\cdot 10^5\)).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1,a_2,...,a_N\) (\(1\leq a_i\leq 10^9\)).

Output

• Gồm một số nguyên duy nhất là giá trị \(F(A)\) mod \(1000000007\).

Example

4
1 2 3 4

50

5
2 4 6 12 3

457

Nguồn bài: CERC 2019