Anh Phú thợ điện đang thực hiện một phiên megalive trên TikTok để tri ân "anh em đội thợ điện". Thay vì bán máy khoan hay kìm cắt, anh quyết định tặng các gói vật tư đặc biệt cho người xem. Trong kho của anh hiện đang có ~N~ gói vật tư, mỗi gói có giá trị là một số nguyên dương khác nhau.

Ban đầu, chỉ số uy tín của anh Phú thợ điện là ~1~. Để làm không khí buổi live thêm "rực cháy", anh liên tục "phát quà" theo quy trình sau:

1. Anh Phú thợ điện nhìn vào giỏ hàng và chọn ra gói vật tư có giá trị nhỏ nhất hiện có, gọi giá trị đó là ~M~.

2. Chỉ số uy tín của anh sẽ ngay lập tức được nhân lên ~M~ lần.

3. Anh Phú hô "Chốt đơn!" và gói vật tư giá ~M~ đó sẽ được tặng đi, không còn trong giỏ hàng nữa.

4. Để bù đắp cho kho hàng, anh Phú thợ điện "vẩy tay" một cái, lập tức tạo ra thêm các gói vật tư mới có giá trị lần lượt là ~1, 2, 3, \dots, M-1~ rồi bỏ lại vào kho (anh Phú thợ điện đã công nhận, các gói vật tư mới được thêm vào không có gói vật tư nào có giá trị trùng với các gói vật tư trong kho).

Anh Phú thợ điện dự định thực hiện thao tác "phát quà" này đúng ~k~ lần. Tuy nhiên, vì mải mê hô "Chốt đơn!", anh đã quên mất chỉ số uy tín hiện tại của mình là bao nhiêu.

Yêu cầu: Hãy giúp anh Phú thợ điện tính toán chỉ số uy tín cuối cùng sau đúng ~k~ lần phát quà. Vì con số này có thể lớn khủng khiếp như hóa đơn tiền điện mùa hè, hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)~ - số lượng gói vật tư ban đầu và số lần anh Phú thợ điện phát quà.

• Dòng thứ hai chứa ~n~ số nguyên ~s[1], s[2], \dots, s[n]~ ~(1 \le s[i] \le 10^9)~ - giá trị của các gói vật tư ban đầu.

Ghi chú: Đảm bảo rằng trong kho luôn có ít nhất một gói vật tư trước mỗi lần thực hiện phát quà.

Output

• Với mỗi test case, in ra một số nguyên duy nhất là chỉ số uy tín của anh Phú thợ điện sau ~k~ lần thao tác, lấy phần dư cho ~10^9 + 7~.

Scoring

Sample Input 1

3 6
5 1 4

Sample Output 1

24