题目描述

有一个大小为$\red{n}$的可重集$\red{S，}$小奇每次操作可以加入一个数$\red{a+b(a,b}$均属于$\red{S)，}$求$\red{k}$次操作后它可获得的$\red{S}$的和的最大值。（数据保证这个值为非负数）

输入格式

第一行有两个整数$\red{n,k}$表示初始元素数量和操作数，第二行包含$\red{n}$个整数表示初始时可重集的元素。

输出格式

输出一个整数，表示和的最大值。答案对$\red{10000007}$取模。

样例

输入样例

2 2
3 6

输出样例

33

提示

对于$\red{30\%}$的数据，有 $\red{n<=10^5，}$$\red{k<=10^5，}$$\red{|ai|<=10^5}$。

对于$\red{100\%}$的数据，有 $\red{n<=10^5，}$$\red{k<=10^9，}$$\red{|ai|<=10^5}$。