Giá trị của một dãy ~B~ là phần tử lớn nhất của ~B~.

Cho một dãy ~A~ gồm ~n~ số nguyên. Hãy tính tổng giá trị của tất cả các dãy con gồm đúng ~k~ phần tử của ~A~.

Dãy con ở đây được lấy theo chỉ số: hai dãy con được coi là khác nhau nếu tập chỉ số được chọn khác nhau, kể cả khi các giá trị trùng nhau. Các phần tử không cần liền nhau.

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra tổng giá trị của tất cả các dãy con độ dài ~k~, đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

4 2
6 7 6 5

Đầu ra:

39

Giải thích: Có ~\binom{4}{2} = 6~ dãy con độ dài ~2~. Giá trị lớn nhất của chúng lần lượt là ~7, 6, 6, 7, 7, 6~, tổng bằng ~39~.

Giới hạn

• ~1 \le k \le n \le 10^5~
• ~1 \le A_i \le 10^9~

Liệt kê mọi dãy con là bất khả thi. Hãy đếm theo phần tử lớn nhất: sắp xếp ~A~ tăng dần, khi đó phần tử ở vị trí ~i~ (đánh chỉ số từ ~0~) là phần tử lớn nhất của đúng ~\binom{i}{k-1}~ dãy con — chọn thêm ~k-1~ phần tử từ ~i~ phần tử đứng trước nó.

Vậy đáp án là ~\sum_{i=0}^{n-1} A_i \cdot \dbinom{i}{k-1}~ (với ~A~ đã sắp xếp).

Việc sắp xếp cũng xử lý luôn các giá trị trùng nhau: mỗi tập chỉ số được đếm đúng một lần, tại vị trí đứng sau cùng của nó trong thứ tự đã sắp xếp.