G. GCD Festivaltime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputMr. Chanek has an array a of n integers. The prettiness value of a is denoted as:\sum_{i=1}^{n} {\sum_{j=1}^{n} {\gcd(a_i, a_j) \cdot \gcd(i, j)}}where \gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y.In other words, the prettiness value of an array a is the total sum of \gcd(a_i, a_j) \cdot \gcd(i, j) for all pairs (i, j).Help Mr. Chanek find the prettiness value of a, and output the result modulo 10^9 + 7!InputThe first line contains an integer n (2 \leq n \leq 10^5).The second line contains n integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^5).OutputOutput an integer denoting the prettiness value of a modulo 10^9 + 7.ExampleInput
5
3 6 2 1 4
Output
77

5
3 6 2 1 4

77 
['math', 'number theory', '*2200']