| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 50 | 25 | 22 | 53.659% |
В очередной раз запутавшись в наложенных проклятьях, заклятьях и прочих магических штуках, Малефисента решила вместо того, чтобы разбираться с ними в течение нескольких дней, отменить их все, а после заколдовать заново тех, кого нужно.
Каждое заклятье можно представить в виде неотрицательного целого числа. Скажем, что $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