Sum of GCD and Maximum Product in Subarrays

Given a non-empty sequence of positive integers \(A = (a_1, a_2, \dots, a_N)\), we define the following functions for any subarray \(A[i \dots j]\) with \(1 \le i \le j \le N\):

• \(G(i,j)=\gcd(a_i, a_{i+1}, \dots, a_j)\)
• \(M(i,j)=\max(a_i, a_{i+1}, \dots, a_j)\)
• \(P(i,j)=G(i,j)\times M(i,j)\)

Define \(F(A)=\sum_{1\le i\le j\le N} P(i,j)\). Your task is to compute \(F(A) \bmod 1\,000\,000\,007\) for a given sequence \(A\).

inputFormat

The first line contains an integer \(N\) denoting the length of the sequence \(A\).
The second line contains \(N\) space-separated positive integers \(a_1, a_2, \dots, a_N\).

\(1 \le N \le 2000\) and \(1 \le a_i \le 10^9\).

outputFormat

Output a single integer which is the value of \(F(A) \bmod 1\,000\,000\,007\).

sample

3
1 2 3

22