시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 15 | 14 | 10 | 90.909% |
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.
Let ti be the time it will take to solve the ith problem. Your strategy for the contest is as follows:
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 109 + 7.
The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 300).
The ith line of the next n lines contains a single integer ti (1 ≤ ti ≤ 1,000,000).
Print, on a single line, a single integer representing the sum of penalty times over all possible orders you read the problems in, modulo 109 + 7.
4 3 1 3 2 1
336
10 2 1000000 2 152 49 93064 438953 438 9238 9065 1274
513850896