Summation over Range Sequences

You are given a sequence g of length n (indexed from 1). In a fictional programming language, there is a statement range(a,b,c) that produces a sequence:

$$ [a,\; a+c,\; a+2c,\; \dots,\; a+k\,c] $$

where k is the largest non-negative integer satisfying $$a + k\,c < b.$$

For example, range(1,7,2) produces the sequence $$[1,3,5].$$

Your task is to compute the value of the following sum modulo $$10^9+7$$:

$$ S = \sum_{a=1}^{n} \sum_{b=a+1}^{n+1} \sum_{c=1}^{n} \; \sum_{i \in \mathrm{range}(a,b,c)} g_i. $$

Note: For each valid triple (a, b, c) (with 1 ≤ a < b ≤ n+1 and 1 ≤ c ≤ n), the sum over i is taken for all indices i in the sequence generated by range(a,b,c).

inputFormat

The first line contains a single integer n — the length of the sequence.

The second line contains n space-separated integers g1, g2, ..., gn.

outputFormat

Output a single integer, the value of S modulo $$10^9+7$$.

sample

3
1 2 3

43