Cho một dãy ~N~ số nguyên dương. Chọn ngẫu nhiên hai chỉ số ~1 \le l, r \le n~. Nếu ~l > r~ thì ta swap hai chỉ số. Trọng số của một đoạn ~[l, r]~ là số giá trị khác nhau trong dãy ~a_l, a_{l + 1}, \ldots, a_r~. Tính Giá trị kì vọng của trọng số nhận được.

Chi tiết về Giá trị kì vọng có thể tìm hiểu ở đây. Ở bài toán này, Giá trị kì vọng có thể hiểu là trung bình cộng của các trọng số nhận được từ tất cả các cách chọn hai chỉ số ~l, r~.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^6)~.

• Dòng thứ hai gồn ~N~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^6)~.

Output

• Gồm một số nguyên là Giá trị kì vọng của trọng số được viết dưới dạng phân số ~\frac{X}{Y}~ chia lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

4
4 2 3 2

Sample Output 1

2

Sample Input 2

7
1 2 8 6 2 8 6

Sample Output 2

918367356

Notes

Ở test ví dụ thứ nhất trên:

• Có ~4~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~1~ là (~1, 1~), (~2, 2~), (~3, 3~), (~4, 4~).

• Có ~8~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~2~ là (~1, 2~), (~2, 1~), (~2, 3~), (~3, 2~), (~2, 4~), (~4, 2~), (~3, 4~), (~4, 3~).

• Có ~4~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~3~ là (~1, 3~), (~3, 1~), (~1, 4~), (~4, 1~).

Từ đó, giá trị kì vọng nhận được là ~\frac{1 \cdot 4 + 2 \cdot 8 + 3 \cdot 4}{16} = 2~.

Ở test ví dụ thứ hai, giá trị kì vọng nhận được là ~\frac{129}{49} \equiv 918367356 \pmod{10^9 + 7}~.