Ở một ngôi trường nọ, có một quy tắc mà học sinh nào cũng biết đó là "ôn thi một đằng kiểm tra một nẻo".

Vào một ngày mưa rào, tâm tình gắt gỏng nên cô của Neko vừa cho ôn dạng bài tìm tích của ~2~ số thì đã cho làm bài kiểm tra và bắt Neko phải tìm ra được tổng của tích tất cả các bộ ~3~ số ~a_i, a_j, a_k~ trong ~n~ số ~(1 \le i < j < k \le n)~. Vì quá sốc văn hóa nên Neko đành phải nhờ bạn lập trình giải giúp bài toán này. Do kết quả có thể là số rất lớn nên Neko yêu cầu bạn phải lấy phần dư khi chia kết quả cho ~10^9 + 7~.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, a_3, ..., a_n~ ~(1 \leq a_i \le 10^6)~.

Output

• Ghi ra tổng của tích tất cả các bộ ~3~ số trong ~n~ số.

Sample Input

5
3 2 5 4 6

Sample Output

580

Subtask

• ~10\%~ số test có ~n \le 500~ và ~a_i \le 10^4~
• ~10\%~ số test tiếp theo có ~n \le 5000~
• ~80\%~ số test còn lại không có điều kiện gì thêm