FFZ's birthday is coming. GTY wants to give a gift to ZZF. He asked his gay friends what he should give to ZZF. One of them said, 'Nothing is more interesting than a number multiset.' So GTY decided to make a multiset for ZZF. Multiset can contain elements with same values. Because GTY wants to finish the gift as soon as possible, he will use JURUO magic. It allows him to choose two numbers a and b($ a,b \in S $), and add $ a + b $ to the multiset. GTY can use the magic for k times, and he wants the sum of the multiset is maximum, because the larger the sum is, the happier FFZ will be. You need to help him calculate the maximum sum of the multiset.
Input
Multi test cases (about 3) . The first line contains two integers n and k ($ 2\leq n \leq 100000 , 1 \leq k \leq 1000000000 $). The second line contains n elements $ a_i $ ($ 1\leq a_i \leq 100000$)separated by spaces , indicating the multiset S .
Output
For each case , print the maximum sum of the multiset ($mod~10000007$).
