Малефисумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В очередной раз запутавшись в наложенных проклятьях, заклятьях и прочих магических штуках, Малефисента решила вместо того, чтобы разбираться с ними в течение нескольких дней, отменить их все, а после заколдовать заново тех, кого нужно.

Каждое заклятье можно представить в виде неотрицательного целого числа. Скажем, что $$$i$$$-му заклятью соответствует число $$$a_i$$$. Тогда, чтобы снять все заклятья сразу, надо найти число $$$$$$\sum\limits_{1 \le i < j < k \le n} a_i \cdot a_j \cdot a_k$$$$$$

Помогите ей поскорее разобраться с этой проблемой. Посчитайте число, необходимое для снятия всех заклятий. Поскольку число может получиться слишком большим, требуется посчитать его по модулю $$$1\,000\,000\,007$$$.

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

В первой строке дано одно целое число $$$n$$$ — количество заклятий ($$$3 \le n \le 10^6$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$, соответствующих заклятьям ($$$0 \le a_i \le 10^6$$$).

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

Выведите требуемое число по модулю $$$1\,000\,000\,007$$$.

Примеры

Входные данные
3
1 2 3
Выходные данные
6
Входные данные
4
0 5 6 7
Выходные данные
210