Today Jinnie is stuck in magic land which has N bags each containing some gold coins. The magical property of magic land is that whenever Jinnie touches exactly M different bags then the bag with maximum amount of coins among M bags is automatically added to the Jinnie's collection.
Now Jinnie wants to know to the total amount of coins he can collect by touching each possible combination of M different bags. Since the collection could be large so Jinnie wants to know the total collection modulo 109+7. Help Jinnie in this magic task.
Input:
The first line of input contains two integers N and M.
The following line of input contains N space separated integers denoting amount of gold coins in each bag.
Output:
The first and only line of output must contain the required number.
Constraints:
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 60
- 0 ≤ Amount of gold coins in each bag ≤ 109
All possible selections of 3 bags are:
[2, 4, 2], [2, 4, 3], [2, 4, 1], [2, 2, 3], [2, 2, 1], [2, 3,
1], [4, 2, 3], [4, 2, 1], [4, 3, 1], [2, 3, 1]
Now if add the maximum coins bag from each selection then we have : 4+4+4+3+2+3+4+4+4+3 = 35
