지우개

승현이는 남이 지우개를 훼손할까 걱정되어 지우개를 직접 만들기로 했다.

승현이는 자연수로 이루어진 수열 $a_1, a_2, \dots, a_n$을 하나 정한다. 이 수열에서 서로 다른 세 위치의 원소 $a_i$, $a_j$, $a_k$를 골라 가로, 세로, 높이가 각각 그 값인 직육면체 지우개를 만들고, 이를 $i-j-k$ 지우개라고 부른다. 단 승현이는 위로 길쭉한 지우개를 좋아하므로 $a_i < a_j < a_k$를 만족해야 한다.

위 그림을 살펴보자. 승현이가 정한 수열을 $a_1 = 3$, $a_2 = 1$, $a_3 = 1$, $a_4 = 2$라고 하자. $1-2-3$ 지우개는 $3 < 1 < 1$이 성립하지 않으므로 만들 수 없다. 반면 $2-4-1$ 지우개는 $1 < 2 < 3$이 성립하므로 만들 수 있다. 이 수열에서 만들 수 있는 지우개는 $2-4-1$ 지우개와 $3-4-1$ 지우개뿐이다.

승현이는 만들 수 있는 지우개의 부피를 모두 더하면 얼마인지 궁금해졌다. 지우개의 부피는 가로, 세로, 높이의 곱이다. 지우개를 쌓아 둘 창고를 설계하려면 이 값이 필요하니, 승현이를 도와주자.

첫째 줄에 수열의 길이 $n$이 주어진다. ($1 \le n \le 100{,}000$)

둘째 줄에 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 차례대로 주어진다. ($1 \le a_i \le 100{,}000$)

첫째 줄에 만들 수 있는 모든 지우개의 부피의 합을 출력한다. 승현이는 프로그램이 제대로 도는지부터 확인하고 싶어 하므로, $1{,}000{,}000{,}007$ ($10^9 + 7$)로 나눈 나머지를 출력한다.

수열이 $a_1 = 3$, $a_2 = 1$, $a_3 = 1$, $a_4 = 2$인 경우를 보자. 만들 수 있는 지우개는 $2-4-1$ 지우개와 $3-4-1$ 지우개뿐이므로, 부피의 합은 $a_2 a_4 a_1 + a_3 a_4 a_1 = 1 \times 2 \times 3 + 1 \times 2 \times 3 = 12$이다.