题目描述

David作为一名优秀的魔术师,精通各种魔术,尤其是变石子的小把戏。

他有一个装着n（n>1）个石子的袋子，每个石子都有一个美丽度beautyi,（美丽度可以为任意整数）他会变m次把戏,每次从袋子里去出两个石子a,b,由这两个石子可以变出新的石子c（a,b不会被消耗）,c的美丽度$beauty_c=beauty_a+beauty_b$。每次操作完,他会a,b,c放回袋子中,继续下一个把戏。

机智的你识破了他的把戏,并计算出m次把戏后Σbeauty（也就是所有石子美丽度之和）最大值maxans，并在mod 10007的意义下输出这个值ans（也就是对答案取模10007，且取模后满足 ）。

输入格式

第一行两个数n,m,表示n个石子,m次把戏。

第二行n个数beautyi,表示n个石子的美丽度。

输出格式

输出ans表示最大值之和取模10007后的答案。

样例数据

输入样例1

3 5
1 -2 -3

输出样例1

1

样例说明

第一次操作取出1,-2,得到{-3,-2,-1,1}.

第二次操作取出1,-1,得到{-3,-2,-1.0,1}.

第三次操作取出1,0,得到{-3,-2,-1,0,1,1}.

第四次操作取出1,1,得到{-3,-2,-1,0,1,1,2}.

第五次操作取出1,2,得到{-3,-2,-1,0,1,1,2,3}.

所有元素和为1.

特别说明

对于负数x的取模也满足x%p = x+a*p ,a可以为任意整数。 例：

-2 模 10007 等于 10005

-23333 模 10007 等于 6688

数据规模与约定

测试点1~3满足beautyi均为正整数.

测试点4~5满足n=2.

测试点6~7满足n,m<=1000. 所有测试点满足n,m<=$10^5$ ,|beautyi|<=$10^8$ .

时间限制：$1 text {s}$

空间限制：$256 text {MB}$