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 bi, is divisible by x and xbi≥x.
Compute ∑i=1nf(ai). As the result can be very large, you should print the value modulo 109+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≤n≤105).
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤105).
Output
Print a single integer — the answer to the problem modulo 109+7.
Sample
Input
Output
5
2 1 6 5 8
34
Let’s look at how f(a1)=f(2) is calculated. There are 3 subsequences which satisfy the given conditions: {6},{6,8},{8}. So, f(a1)=3.