Задача №113796. Смишенное произведение
Миша очень любит изобретать новые операции. Недавно он изобрёл новую операцию, которую он в честь себя назвал смишенным произведением.
Смишенное произведение набора различных натуральных чисел a1, a2, ..., an устроено следующим образом. Рассмотрим все возможные упорядоченные пары (ai, aj) различных чисел этого набора. Для каждой пары запишем эти числа подряд без пробела, получив новое число bij. Смишенным произведением чисел из исходного набора Миша называет сумму всех значений bij.
Помогите Мише посчитать смишенное произведение заданного набора чисел. Миша хочет вычислить его по модулю 109 + 7.
Первая строка содержит одно натуральное число n — количество чисел в наборе (2 ≤ n ≤ 105).
Вторая строка содержит n различных натуральных чисел a1, a2, ..., an — числа набора (1 ≤ ai ≤ 108).
Выведите одно число — остаток от деления смишенного произведения заданных чисел на число 109 + 7.
3
1 3 10
668
В примере из условия есть шесть возможных пар, получаются следующие значения bij: 13, 31, 101, 103, 110, 310, их сумма равна 668.