Be Geeks!

Xem PDF



Thời gian:
Java 3.0s
Python 4.0s
Bộ nhớ:
Java 512M
Python 512M

Tác giả:
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input
4
1 2 3 4
Output
50

Test 2

Input
5
2 4 6 12 3
Output
457

Nguồn bài: CERC 2019


Bình luận