19840번 - Misha's Product 다국어

문제

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$.

제한

힌트

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.