Mathemagic
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 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. Similarly: f(a2)=f(1)=31;f(a4)=f(5)=0;f(a3)=f(6)=0f(a5)=f(8)=0 ∑i=1nf(ai)=(3+31+0+0+0)=34 And 34 (mod 109+7)=34. Hence the answer is 34 |