题目描述

小核桃检测到 n 股能量波动(n的范围更大了)，强度分别是 a[1] 到 a[n]。这些能量汇合到一起，形成了一股新的能量，能量总和是下面这个式子的结果。

请你编写一个程序计算输出新能量的大小，结果对1000000007取模。

输入格式

第 1 行一个正整数 n，表示能量波数量。

第 2 行 n 个正整数，为能量波强度，即a[1],a[2]...a[n]。

输出格式

汇合后的新能量总和。

样例1

5
1 2 3 4 5

117

样例2

4
3 2 3 5

76

数据范围

1 ≤ n ≤ 5000000; 1 ≤ a[i] ≤ 100000。