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}\)
5 3 2 4 2 3 1
35
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor