One day Ananya Pandey arrives at Kapil Sharma Show for the promotion of movie "Student of the year 2".As Kapil always makes fun of everyone So Ananya decided to make fun of Kapil sharma this time.She gives an array of $N$ integers to Kapil and wants the summation of $GCD$ of all subarray. 

$\displaystyle\sum_{i=1}^{N}$ $\displaystyle\sum_{j=i}^{N} GCD(i...j)$

Here, $GCD$ denotes the greatest common divisor of a set of numbers and $GCD(i...j)=GCD(i,i+1,i+2.......j-1,j)$

$GCD(K,K)=GCD(0,K)=GCD(K,0)=K$.

This summation may be very large so take modulo with $(10^9+7)$.
As you know Kapil Sharma is weak in Math So he needs your Help!!!

Input
First line contains a single Integer $N (1<=N<=10^5)$, length of array
Second line contains $N$ integers, $x_i$ $(1<=x_i<=10^{12})$represents ^$i$th element in array.

Output
A single Integer i.e. summation of $GCD$ of all subarray modulo $(10^9+7)$.