Description

Removal Game, bibibi.

If string A is a suffix of string B, we call string b is a good string for A.Now Tom has n strings.The number is string[1],string[2]....string[n].The 1,2,3...n is the number of these strings. Now for all string[i], Tom wants to know the kth number of good string for string[i]. But Ann don't want you to solve the problem, because it's too hard.She gives another easy problem: There is a multiset. At first there are n numbers in the multiset. Every day, it will add a number.The number is equal A + B.The A and B should in the multiset. Ann wants to know after K days, the max sum of the multiset will be. Please help she.

Format

Input

There are multiple test cases. For each case,The first line is a integer n,k (n<=100000, k<=1e9) , The second line will be n numbers ai (|ai|<=1e5),there are no float.

Output

For each test case, Answer the question after mod 10000007.

Samples

3 1
3 3 6

21

Hint