У Джона Доу есть массив a из n элементов. Джон хочет найти величину , то есть сумму квадратов разностей элементов массива по всем возможным парам i, j.

Например для массива {1, 2, 3} такая величина будет равна (1 - 1)2 + (1 - 2)2 + (1 - 3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 - 1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 + 0 = 12

Найдите остаток от деления S на 10⁸.

Напомним, как работать с остатками от деления. Остаток от деления числа a на число b обозначим как . Верны следующие соотношения:

• 
• 
• (для a ≥ b).

К примеру, вы хотите посчитать величину . Перемножить эти три числа в стандартном типе данных вам не удастся, но можно воспользоваться первым соотношением и посчитать сначала Теперь можно перемножить получившееся число и 107 + 3 и получить .

В первой строке записано целое число n (1 ≤ n ≤ 10⁶) — количество элементов массива. Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ a_i ≤ 10⁹).

Выведите остаток от деления S на 10⁸.

Входные данные

3
1 2 3

12

5
100 1 9 1 3

74928

2
1000000000 1

2

Тесты поделены на несколько групп, но оцениваются отдельно.

• n, a_i ≤ 1000 – 10 баллов
• n ≤ 5000 – 10 баллов
• n ≤ 10⁶ a_i≤ 5000 – 30 баллов
• Без дополнительных ограничений — 50 баллов

Например, если вы решили задачу для n ≤ 5000 и произвольных a_i вы получите 20 баллов (первая и вторая группы).

Загруженные файлы:

Примечание учителя: