Sau một chuỗi thua cá cược khi đặt hết niềm tin vào Hà Lan, Bồ Đào Nha, Pháp, Đức ... thì giờ đây algorit đã gần như mất hết tất cả, từ nhà cửa, xe cộ, sổ đỏ, tiền bạc, thậm chí cả người yêu cũng đi theo thằng khác. Có thể nói algorit bây giờ chỉ còn đúng cái nịt, nhưng với châm ngôn là còn thở còn gỡ, lần này algorit sẽ đánh cược cái nịt cuối cùng vào trận bóng tối nay.

Để khả năng cá cược thành công cao hơn thì algorit phải tính ra tỉ lệ tỉ số. Ban đầu ta có một dãy số gồm \(N\) phần tử được đánh số theo thứ tự từ \(1\) đến \(N\). Bên cạnh đó ta cũng được cung cấp một số nguyên dương \(K\leq N\).

Thực hiện lần lượt các bước sau:

• Bước 1 : Khởi tạo giá trị \(Sum := 0\)

• Bước 2 : Chọn ra một tập hợp mới, không được trùng với tập hợp nào đã chọn trước đó, gồm \(K\) số \(1 \leq i_{1} \lt i_{2} \lt i_{3} \lt ....\lt i_{k} \leq N\)

• Bước 3 : Tính giá trị \(P = a[i_{1}] * a[i_{2}] * a[i_{3}] * ........ * a[i_{k}]\)

• Bước 4 : Thực hiện tăng **Sum ** lên \(P\) (gán \(Sum:=Sum+P\))

• Bước 5 : Nếu vẫn còn tập hợp chưa được chọn thì lặp lại Bước 2, nếu không thì thực hiện Bước 6

• Bước 6 : Xuất phần dư của **Sum ** khi chia cho \(10^9+7\)

Tỉ lệ tỉ số là kết quả cuối cùng của bước \(6\), nếu tính ra tỉ lệ này thì algorit có khả năng \(99\%\) sẽ thành công trong lần cá cược này, anh sẽ giành lại những gì đã mất. Vì vậy các bạn chuyên tin hãy giúp anh ấy tìm lại sổ đỏ, tiền bạc, xe cộ nhé !

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \(N\) và \(K\).

• Dòng tiếp theo gồm \(N\) số nguyên dương \(a[i_{1}], a[i_{2}], a[i_{3}], .... , a[i_{N}] \leq 10^9\)

Output

• Gồm một số duy nhất là kết quả ở Bước 6

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(K=2\)

• Subtask \(2\) (\(10\%\) số điểm): \(K=3\)

• Subtask \(3\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 3 4 5

85