28744번 - Малефисумма 다국어

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

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