You are given \(N\) bags and each bag contains gold coins. You must select \(M\) distinct bags. The bag with the maximum amount of coins among the \(M\) bags is added to a set \(S\).

Write a program to calculate the total number of set \(S\) over each possible combination of \(M\) bags. Since the output can be large, print the answer modulo \( 10^{9}+7 \)

Input format

• First line: Two space-separated integers \(N\) and \(M\)
• Second line: \(N\) space-separated integers denoting the amount of gold coins in each bag

Output format

Print the total value of \(S\) modulo \( 10^9+7 \) over each possible combination of \(M\) bags.

Constraints

\(1 \le N \le 10^{5}\)
\(1 \le M \le 60\)
\(0 \le Amount\;of\; gold \;coins \;in \;each \;bag \le 10^{9}\)