Sau khi áp dụng sáu chương trước bây giờ bạn đã thành công tán crush, nhiệm vụ của bạn bây giờ của bạn là chia crush ra thành từng phần à nhầm... chia công việc ra thành từng phần để tiện cho cuộc hẹn đầu tiên của bạn với crush của mình.

Cụ thể như sau, bạn đang có $n$ công việc, bạn cần chia $n$ công việc này ra thành $k$ phần liên tiếp, nếu gọi công việc thứ $i$ có độ phức tạp là $a_i$ thì lúc đó khoản tiền bạn nhận được khi làm $n$ công việc là tích của tổng độ phức tạp các công việc trong mỗi nhóm.

Ví dụ, khi chia $4$ công việc $[1;\ 2;\ 3;\ 4]$ thành $2$ phần là $[1;\ 2]$ và $[3;\ 4]$ thì tổng thời gian làm hết các công việc trên là $(1 + 2)\times (3 + 4) = 3\times 7 = 21$.

Sếp của bạn (giả sử là tôi) đã giao cho bạn $n$ công việc và yêu cầu bạn chia nó thành $k$ phần để làm. Bạn cần tính toán số tiền lớn nhất có thể nhận được để có thể đi chơi với crush (có thể là người yêu tương lai) của bạn một cách xa xỉ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên $n$ và $k$ - số lượng công việc và số lượng nhóm công việc cần chia. $(1\leq n\leq 2.10^5,\ 1\leq k\leq min(20, n))$
• Dòng thứ hai gồm $n$ số nguyên $a_i\ (1\leq i\leq n)$ với $a_i$ là độ phức tạp của công việc thứ $i$. $(1\leq a_i\leq 10^9)$

Output

• Gồm một số nguyên duy nhất là số tiền nhiều nhất có thể nhận được bạn làm $n$ công việc chia vào $k$ nhóm. Trong trường hợp kết quả quá lớn hãy in ra kết quả chia lấy dư cho $10^9 + 7$ (modulo $10^9 + 7$). Lưu ý rằng kết quả ở đây không phải là kết quả lớn nhất sau khi mod.

Subtasks

• Subtask 1: Đảm bảo $n\leq 15$ và $a_i\leq 10$. (20 điểm)
• Subtask 1: Đảm bảo $n\leq 1000$. (80 điểm)
• Subtask 2: Không có ràng buộc gì thêm. (300 điểm)

Example

4 2
1 2 3 4

24