В очередной раз запутавшись в наложенных проклятьях, заклятьях и прочих магических штуках, Малефисента решила вместо того, чтобы разбираться с ними в течение нескольких дней, отменить их все, а после заколдовать заново тех, кого нужно.
Каждое заклятье можно представить в виде неотрицательного целого числа. Скажем, что $$$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