Limits 1s, 512 MB

You are given a sequence aa of length nn.

For an arbitrary number xx, f(x)f(x) can be defined as the number of non-empty subsequences bb of aa such that each element of bb, denoted by bib_i, is divisible by xx and bixx\frac{b_i}{x}\ge x.

Compute i=1nf(ai)\sum_{i=1}^{n}{f(a_i)}. As the result can be very large, you should print the value modulo 109+710^9+7.


  • A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input

The first line contains a single integer nn (1n1051 \le n \le 10^5).

The second line of each test case contains nn integers a1,a2,,ana_1, a_2,…, a_n (1ai1051 \le a_i \le 10^5).

Output

Print a single integer — the answer to the problem modulo  109+710^9+7.

Sample

InputOutput
5
2 1 6 5 8
34

Let’s look at how f(a1)=f(2)f(a_1)=f(2) is calculated. There are 3 subsequences which satisfy the given conditions: {6},{6,8},{8}\{6\},\{6,8\}, \{8\}. So, f(a1)=3f(a_1) = 3.

Similarly: f(a2)=f(1)=31;f(a3)=f(6)=0f(a4)=f(5)=0;f(a5)=f(8)=0\begin{matrix}f(a_2) = f(1) = 31 ;& f(a_3) = f(6) = 0 \\ f(a_4) = f(5) = 0 ; & f(a_5) = f(8) = 0 \\\end{matrix}

i=1nf(ai)=(3+31+0+0+0)=34\sum_{i=1}^{n} f(a_i) = ( 3+31+0+0+0 ) = 34

And 34 (mod 109+7)=3434 \text{ (mod } 10^9+7\text{)} = 34. Hence the answer is 34\boxed{34}


Submit

Login to submit.

Statistics

78% Solution Ratio
AlfehsaniEarliest, Aug '22
LU_MisbahFastest, 0.0s
arafraihan7Lightest, 5.5 kB
MrBrionixShortest, 519B
Toph uses cookies. By continuing you agree to our Cookie Policy.