Mr. 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\)!
Output
Output an integer denoting the prettiness value of \(a\) modulo \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 6 2 1 4
|
77
|