# Mathemagic

SEC Inter University Juni...
Limits 1s, 512 MB

You are given a sequence $a$ of length $n$.

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

Compute $\sum_{i=1}^{n}{f(a_i)}$. As the result can be very large, you should print the value modulo $10^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 $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2,…, a_n$ ($1 \le a_i \le 10^5$).

## Output

Print a single integer — the answer to the problem modulo  $10^9+7$.

## Sample

InputOutput
5
2 1 6 5 8

34


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

Similarly: $\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}$

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

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