말레피센트 합

말레피센트는 저주, 주문, 그 밖의 마법 물건이 또다시 뒤엉켜 버리자, 며칠에 걸쳐 풀기보다 모두 한꺼번에 해제하고 필요한 대상에게만 저주를 다시 걸기로 했다.

각 저주는 음이 아닌 정수로 나타낼 수 있다. i번째 저주에 대응하는 수를 a_i라 하자. 모든 저주를 한 번에 해제하려면 다음 값을 구해야 한다.

$\sum_{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$).

둘째 줄에는 각 저주에 대응하는 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($0 \le a_i \le 10^6$).

구한 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.