ICPC PACNW 2016 D - Contest Strategy

View as PDF

Submit solution

Points: 25
Time limit: 1.8s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Python

You are participating in the Association for Computing Machinery's Intercollegiate Programming Competition (ACM ICPC). You must complete a set of n problems. Since you are an experienced problem solver, you can read a problem and accurately estimate how long it will take to solve it, in a negligible amount of time.

Le t_i be the time it will take to solve the ith problem. Your strategy for the contest is as follows:

  1. Read k random problems
  2. Choose a problem that you have read that will take the shortest time to solve (if there are ties, choose any of them arbitrarily).
  3. Solve the problem, and read a random unread problem (if there is any).
  4. If there are still unsolved problems, go back to step 2.

Your penalty time for the contest is defined by the sum of submission times for all the problems. Of course, your penalty time depends on the order in which the problems are read. What is the sum of penalty times, over all n! possible different orders you read the problems in? Since the result can be very large, find the answer modulo 10^9 + 7.

Input

The first line of input contains two space-separated integers n and k (1 \le k \le n \le 300).

The ith line of the next n lines contains a single integer t_i (1 \le t_i \le 1\,000\,000).

Output

Print, on a single line, a single integer representing the sum of penalty times over all possible orders you read the problems in, modulo 10^9 + 7.

Sample Input 1

4 3
1
3
2
1

Sample Output 1

336

Sample Input 2

10 2
1000000
2
152
49
93064
438953
438
9238
9065
1274

Sample Output 2

513850896
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.