Малефисумма

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

Каждое заклятье можно представить в виде неотрицательного целого числа. Скажем, что $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$.