VOGCDSUM - Tổng ước chung lớn nhất

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Giáo sư Honest là một tay bịp bợm có hạng trong giới khoa học. Ngày hôm qua, hắn vừa tuyên bố rằng đã phát minh ra thuật toán tính ước chung lớn nhất của một dãy số có độ phức tạp O(1 / N), tức là input càng lớn thì thuật toán chạy càng nhanh.

Trong báo cáo khoa học của mình, Honest bày ra thí nghiệm như sau:

Cho một dãy số gồm N số nguyên dương. Honest tính tổng của các ước chung lớn nhất của tất cả các dãy con liên tiếp của dãy số trên (dãy con liên tiếp của một dãy số N phần tử được định nghĩa là dãy con chứa phần tử thứ L, L + 1, ..., R với 1 ≤ L ≤ R ≤ N).

Honest tuyên bố rằng hắn có thể thực hiện thao tác vừa rồi trong O(N) bằng cách áp dụng thuật toán tính ước chung lớn nhất của một dãy số trên tất cả N * (N + 1) / 2, tức là O(N 2 ), dãy con liên tiếp của dãy số. Vì thế, thuật toán của hắn ta có độ phức tạp là O(1 / N).

"Không thể nào có chuyện như vậy!!!". Hội đồng khoa học của diễn đàn VNOI muốn lật tẩy trò lừa trẻ con của Honest. Tuy nhiên thì đầu tiên họ cần tìm ra cách để thực hiện lại thí nghiệm của Honest với tốc độ nhanh nhất có thể. Các bạn hãy giúp in ra số dư của kết quả thí nghiệm mà Honest đã tiến hành khi chia cho 10 9 + 7 nhé.

Input

  • Dòng thứ nhất chứa số nguyên N .
  • Dòng thứ hai chứa N số của dãy A .

Output

  • Một số duy nhất là phần dư của kết quả tìm được khi chia cho 10 9 + 7.

Giới hạn

  • Subtask 1 (15%): 1 ≤ N ≤ 100, 1 ≤ A i ≤ 10 12
  • Subtask 2 (15%): 1 ≤ N ≤ 5000, 1 ≤ A i ≤ 10 12
  • Subtask 3 (30%): 1 ≤ N ≤ 10 5 , 1 ≤ A i ≤ 200
  • Subtask 4 (40%): 1 ≤ N ≤ 10 5 , 1 ≤ A i ≤ 10 12
  • Thời gian chạy cho subtask 1 và 2 là 1s, subtask 3 và 4 là 3s.

Chấm điểm

  • Trong thời gian thi, bài của bạn sẽ chỉ được chấm với duy nhất 1 test có trong đề bài.

Ví dụ

Input:

4
3 6 4 8

Output:

34

  • Người up: voj
  • Nguồn bài: VNOI Online 14 - Nguyễn Tấn Sỹ Nguyên