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\left(a_i, a_{i+1},..., a_j\right)\) với \(1\leq i\leq j\leq N\).

Đặt \(M(i, j)=\max\left(a_i, a_{i+1},..., a_j\right)\) 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)=\sum 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.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\).

Ví dụ:

Input:

4
1 2 3 4

Output:

50

Input:

5
2 4 6 12 3

Output:

457