(tonggiatri.*)

Cho dãy số nguyên dương \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\). Một bộ ba là bộ gồm ba số nguyên \(a_{i},\ a_{j},\ a_{k}\) với \(1 \leq i < j < k \leq n\). Giá trị của bộ ba này được tính bằng tích \(a_{i}\ \times \ a_{j}\ \times \ a_{k}\).

Yêu cầu: Hãy tính tổng giá trị của tất cả các bộ ba khác nhau. Hai bộ ba \(a_{i},\ a_{j},\ a_{k}\) và \(a_{u},\ a_{v},\ a_{w}\) được gọi là khác nhau nếu \(i\
eq \ u\) hoặc \(j\
eq \ v\) hoặc \(k\
eq \ w\). Do con số này có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho \(10^{9}\ + \ 7\)

Dữ liệu:

+ Dòng đầu tiên chứa số nguyên dương \(n\ (n \leq 10^{6})\)

+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\ (a_{i}\ \leq \ 10^{5}\ \forall\ i)\) cách nhau bằng dấu trống (space)

Kết quả:

+ Ghi ra một số nguyên duy nhất là kết quả tìm được

Ví dụ:

Ràng buộc:

+ 2 tests có \(n\ \leq \ 100,\ a_{i}\ \leq \ 10\ \forall i\);

+ 2 tests tiếp theo có \(500\ < \ n\ \leq \ 5000\)

+ 2 tests còn lại có \(5000\ < \ n\ \leq \ 10^{6}\ \)