Description

【题目表述】

有一个大小为 $n$ 的序列 $a$，每次可以在序列末尾加入一个数 $a_i+a_j$（$i\ne j$）。求 $k$ 次操作后 $a$ 序列的和的最大值。

【输入格式】

第一行有两个正整数 $n,k$，表示初始元素数量和操作数。

第二行包含 $n$ 个整数，表示序列 $a$。

【输出格式】

输出一个整数，表示和的最大值。答案对 $10^7 +7$ 取模。

【输入样例】

2 2
3 6

33

【数据规模与约定】

对于 $100\%$ 的数据，有 $n\le 10^5$，$k\le 10^9$，$\left | a_i \right | \le 10^5$。

保证所有最终答案为非负数。