Set of coins | Practice Problems

Set of coins

★★★★★

2.3

3 votes

Ready, Grammar-Verified, Recruit, Approved, Grammar-Verified, Ready, Recruit, Approved, Combinatorics, Hard, Basics of Combinatorics, Basic Programming, Combinatorics basics, Grammar-Verified, Mathematics, Mathematics

Details

Submissions

Discussion

Editorial

Problem

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}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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