Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
Be Geeks!
begeeks.c, begeeks.cpp, Begeeks.java, begeeks.py
The musical band Be Geeks! got its name by no accident, as all the members are genuine math
geeks. Among others, they love examining various properties of number sequences. Let's see an
example of their subject of interest.
Let
A be a nonempty sequence of positive integers, A = (a1, a2, ..., aN ).
Let
G(i, j) = gcd(ai, ai+1, . . . , aj ), where 1 ≤ i ≤ j ≤ N .
Let
M (i, j) = max(ai, ai+1, . . . , aj ), where 1 ≤ i ≤ j ≤ N .
Let
P (i, j) = G(i, j) · M (i, j), where 1 ≤ i ≤ j ≤ N .
P
Let
F (A) =
(i, j) over all pairs of integers 1 ≤ i ≤ j ≤ N .
The function gcd stands for the greatest common divisor of the given values. The greatest
common divisor of a nonempty sequence of integers is the biggest integer which divides each
integer in the sequence evenly.
Input Specification
The first line contains one integer N (1 ≤ N ≤ 2 · 105). The next line contains N integers
a1, a2, . . . , aN (1 ≤ ai ≤ 109 ).
Output Specification
Print the value of F (A) modulo 1 000 000 007.
Output for Sample Input 1
Sample Input 1
50
4
1234
Sample Input 2
Output for Sample Input 2
5
457
2 4 6 12 3
