시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB31141451.852%

문제

Misha really loves to invent new operations. Recently he has invented the new operation, that he has named Misha's product after himself.

Misha's product of the set of different integer numbers $a_1, a_2, \ldots, a_n$ is defined as follows. Consider all possible ordered pairs $(a_i, a_j)$ of different numbers from this set. For each pair write these numbers one after another without a space, and get a new number $b_{ij}$. Misha's product of the initial set is the sum of all values $b_{ij}$.

Help Misha to calculate Misha's product for the given set of integers. Misha wants to calculate it modulo $10^9 + 7$.

입력

The first line contains one integer $n$ --- the number of elements in the set ($2 \le n \le 10^5$).

The second line contains $n$ different integers $a_1, a_2, \ldots, a_n$ --- numbers from the set ($1 \le a_i \le 10^8$).

출력

Output one number --- Misha's product of the given set of numbers, modulo $10^9 + 7$.

예제 입력 1

3
1 3 10

예제 출력 1

668

힌트

There are six possible pairs in sample test, the following values $b_{ij}$ are obtained: 13, 31, 101, 103, 110, 310, their sum is equal to 668.