Sample Input

4 2
10 20 30 40

Sample Output

100

Giải thích

Có tổng cộng 6 cách chọn:
10 20
20 30
30 40
10 30
20 40
10 40
Tổng của chúng : 
10+10+10+20+20+30=100

Sample Input

3 1
1 2

Sample Output

3

Giải thích

Có 3 cách hoán vị là:

1) 2 1 3

2) 2 3 1

3) 3 1 2

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.

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~.

Dữ liệu vào

• 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~

Kết quả

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

Giới hạn

• 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~.

Sample Input

4 2
10 20 30 40

Sample Output

100

Giải thích

• Có tổng cộng 6 cách chọn:

  1. 10 20
  2. 20 30
  3. 30 40
  4. 10 30
  5. 20 40
  6. 10 40
  
  Tổng của chúng : 10+10+10+20+20+30=100.