Oo rất thích việc giải quyết các bài toán. Vào một ngày trong chuỗi những ngày phong tỏa do COVID-19, Oo phải giải quyết bài toán sau: "Cho các điểm trên mặt phẳng tọa độ \(\text{Oxy}\), điểm thứ \(i\) có tọa độ \((2019-a_i,2a_i)\). Hãy tìm hai điểm có khoảng cách lớn nhất trong các cặp điểm được tạo ra bởi các điểm trên và in ra bình phương khoảng cách của cặp điểm đó".

Sau 10 ngày nghiên cứu mệt mỏi, cuối cùng Oo đã đưa ra một công thức khoảng cách giữa hai điểm bất kỳ trên mặt phẳng tọa độ. Bình phương khoảng cách giữa hai điểm \((x_1,y_1)\) và \((x_2,y_2)\) là \((x_1-x_2)^2+(y_1-y_2)^2\). Từ ý tưởng thiên tài đó, Oo đã code ra một lời giải "thiên tài". Không may mắn thay, lời giải đó quá dài để viết ra ở đây nhưng Oo vẫn tự hào nói với bạn cái cốt lõi của ý tưởng: Duyệt qua tất cả các cặp điểm và tìm ra cặp điểm tối ưu. Phần chứng minh của công thức và phần code sẽ do người làm tự thân vận động nhé :).

Bất ngờ thay, Oo nhận ra rằng giới hạn của bài toán là \(10^5\). Nhưng giống như lần trước, Oo đã không tốn quá nhiều thời gian để nghĩ ra một ý tưởng thiên tài khác: thuật toán ngẫu nhiên (randomization algorithm). Nghe có vẻ đáng sợ nhỉ ? Đừng lo !! Oo đã cung cấp lời giải cho điều này như sau: Chọn ra \(k\) điểm bất kỳ từ \(n\) điểm trên và sử dụng lời giải bên trên cho \(k\) điểm đã chọn này. Nhưng chúng ta phải chọn như thế nào ? Vâng, sau \(9954\) thí nghiệm, Oo có thể tự tin nói với bạn rằng \(k\) sẽ không bao giờ vượt quá \(5000\).

Không quá bất ngờ, code trên của Oo đã bị Wrong Answer vài lần. Nhưng điều đó không có vấn đề gì vì Oo đã giải quyết được bài toán đầy thử thách trên. Bây giờ là cơ hội của bạn để áp dụng những gì bạn đã học được qua quá trình giải quyết của Oo. Đây là bài toán dành cho bạn: Hãy tìm giá trị in dự kiến của code của Oo. Quá dễ phải không ? À mà này, không có gợi ý gì đâu nhá, cho gợi ý hết thì mất vui rồi :(.

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\) \((n \le 10^5, k \le \min (5000, n))\) -- số \(n\) và \(k\) trong code của Oo.
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^9)\)

Output

• Biết rằng giá trị đó có thể viết dưới dạng \(P/Q\). In ra giá trị \(f = P \times Q^{-1} \mod (10^9+7)\)

Example

4 3
1 2 3 4 

500000036

2 2
2 3 

5