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

Автор:ВКОШП 2017   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Смишенное произведение набора различных натуральных чисел a1, a2, …, an устроено следующим образом. Рассмотрим все возможные упорядоченные пары (ai, aj) различных чисел этого набора. Для каждой пары запишем эти числа подряд без пробела, получив новое число bij. Смишенным произведением чисел из исходного набора Миша называет сумму всех значений bij.

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

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

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

Вторая строка содержит n различных натуральных чисел a1, a2, …, an — числа набора.

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

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

Ограничения

2 ≤ n ≤ 105

1 ≤ ai ≤ 108

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

Стандартный вход Стандартный выход
1
3
1 3 10
668

0.088s 0.014s 15