Задача 4E. Смишенное произведение ≡

Условие

Миша очень любит изобретать новые операции. Недавно он изобрёл новую операцию, которую он в честь себя назвал смишенным произведением.

Смишенное произведение набора различных натуральных чисел a₁, a₂, …, a_n устроено следующим образом. Рассмотрим все возможные упорядоченные пары (a_i, a_j) различных чисел этого набора. Для каждой пары запишем эти числа подряд без пробела, получив новое число b_ij. Смишенным произведением чисел из исходного набора Миша называет сумму всех значений b_ij.

Помогите Мише посчитать смишенное произведение заданного набора чисел. Миша хочет вычислить его по модулю 10⁹ + 7.

Формат входных данных

Первая строка содержит одно натуральное число n — количество чисел в наборе.

Вторая строка содержит n различных натуральных чисел a₁, a₂, …, a_n — числа набора.

Формат выходных данных

Выведите одно число — остаток от деления смишенного произведения заданных чисел на число 10⁹ + 7.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁸

Примеры тестов

3
1 3 10

668