Cho một mảng ~A~ có ~n~ phần tử, xét tất cả các đoạn con (không liên tiếp) có ~K~ phần tử của ~A~, tính tổng của các số lớn nhất của các đoạn con này và modulo ~10^9 + 7~.

Input: file SOXO.INP có cấu trúc

Dòng đầu: 2 số nguyên ~n, K~ ~(1 ≤ n ≤ 10^5; 1 ≤ K ≤ 50)~

Dòng thứ hai: mảng ~A~. ~(1 ≤ A_i ≤ 10^6)~

Output: ghi vào file SOXO.OUT tổng tìm được

VÍ DỤ:

Input

4 2
6 7 6 5

Output

39