An có một hộp gồm \(N\) quả bóng, trên mỗi quả bóng được viết một số nguyên dương (các số này không nhất thiết phải khác nhau). An chọn 1 tập hợp \(K\) quả bóng, đánh dấu tập hợp này, đặt chúng lại vào hộp và tiếp tục quá trình này cho đến khi tất cả các tập hợp như trên được đánh dấu. Với mỗi tập hợp như vậy, An ghi lại hiệu giữa số lớn nhất và số bé nhất trong nó.

Lưu ý: 2 tập khác nhau nếu có ít nhất 1 quả bóng thuộc tập này và không thuộc tập kia.

Yêu cầu: Bạn hãy tính tổng tất cả các số được An ghi lại. In ra số dư của kết quả khi chia cho \(10^9+7\).

Input

• Dòng đầu chứa 2 số nguyên dương \(N\) và \(K\).
• Dòng tiếp theo chứa \(N\) số được ghi trên bóng.
• Trong đó \(1 \leq K \leq N\), các số trên bóng \(\leq 10^9\)

Output

• Ghi một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5000\).
• Subtask \(3\) (\(50\%\) số điểm): \(N \leq 10^5\).

Example

4 2
10 20 30 40 

100