Trong một buổi hòa nhạc, âm thanh từ một nhạc cụ cụ thể được ghi lại và biểu diễn dưới dạng một chuỗi các mẫu số liệu, bao gồm ~n~ thời điểm. Tại mỗi thời điểm ~i~, chúng ta có một giá trị ~A_i~ , được gọi là cường độ âm tại thời điểm đó. Mỗi ~A_i~ tương ứng với biên độ dao động của sóng âm tại thời điểm ~i~. Để phân tích sự phức tạp và đa dạng của âm thanh này, các nhà nghiên cứu âm học đã đưa ra khái niệm "độ biến thiên âm".

Độ biến thiên âm giữa hai thời điểm ~i~ và ~j~ (với ~i \le j~) được định nghĩa là số lượng các mức cường độ âm khác nhau xuất hiện trong khoảng thời gian từ thời điểm ~i~ đến thời điểm ~j~ (bao gồm cả thời điểm ~i~ và ~j~). Chúng ta gọi số này là hàm ~f(i,j)~.

Ví dụ, nếu chuỗi cường độ âm từ thời điểm ~i~ đến ~j~ là ~[1,2,1,3]~, thì các mức cường độ âm khác nhau xuất hiện là ~1,2,3~. Do đó, độ biến thiên âm ~f(i,j)=3~.

Để đánh giá tổng thể sự biến đổi của âm thanh trong suốt buổi hòa nhạc, các nhà nghiên cứu muốn tính toán tổng bình phương của tất cả các độ biến thiên âm có thể có. Tổng này được gọi là "chỉ số biến thiên âm", kí hiệu ~\Delta f~.Nó được xác định bằng cách xét tất cả các cặp thời điểm ~(x,y~) sao cho ~(1 \le x \le y \le n)~, tính độ biến thiên âm ~f(x,y)~ cho mỗi cặp, lấy bình phương của nó, và sau đó cộng tất cả các bình phương này lại

Hay nói cách khác, ~\Delta f~ được tính như sau: $$ \Large \Delta f=\sum_{x=1}^{n} \sum_{y=x}^{n} f(x,y)^2 $$

Hãy tính ~\Delta f~ giúp các nhà nghiên cứu âm học nhé

Vì ~\Delta f~ có thể rất lớn nên hãy lấy dư với ~10^9+7~.

Input

Dòng đầu tiên là số nguyên ~n~ ~(1 \le n \le 10^5)~

Dòng tiếp theo là ~n~ số nguyên ~A_i~ ~(1 \le A_i \le 10^5, \forall i \in [1,n])~

Output

Một dòng duy nhất là ~\Delta f~ chia dư cho ~10^9+7~

Subtask

• Subtask 1 : ~20\%~ số điểm có ~A_i \neq A_j~ ~\forall~ ~i,j \in [1,n]~ , ~i \neq j~
• Subtask 2: ~30\%~ số điểm có ~n \le 10^3~
• Subtask 3: ~50\%~ số điểm còn lại không có giới hạn gì thêm

Sample Input

3
1 2 3

Sample Output

20

Giải thích

~f(1,1)~ ~=1^2~

~f(1,2)~ ~=~ ~2^2~

~f(1,3)~ ~=~ ~3^2~

~f(2,2)~ ~=~ ~1^2~

~f(2,3)~ ~=~ ~2^2~

~f(3,3)~ ~=~ ~1^2~

~\Longrightarrow~ ~S=1^2 + 2^2 + 3^2+ 1^2 + 2^2 + 1^2=20~