Contest Strategy

You are taking part in the ACM International Collegiate Programming Contest (ICPC), where you have to solve all $n$ problems. Reading a problem takes no time, and once you have read it you know exactly how long solving it takes. Solving problem $i$ takes $t_i$.

Your strategy during the contest is this.

1. Read $k$ random problems.
2. Among the problems you have read but not solved, choose one whose solving time is smallest. If several of them tie, choose any one.
3. Solve it, then read one random unread problem if any is left.
4. If unsolved problems remain, go back to step 2.

The submission time of a problem is the time that has passed when you finish solving it, that is, the total solving time of every problem you have solved up to and including that one. The penalty of the contest is the sum of the submission times of all $n$ problems.

One read order is one permutation of the $n$ problems. You read the first $k$ problems of the permutation at the start, and after solving a problem you read the next problem of the permutation. The penalty depends on the read order, and there are $n!$ read orders. Add up the penalty over all $n!$ of them and print the sum modulo $10^9+7$.

When several read problems tie for the smallest solving time in step 2, the penalty is the same whichever one you choose, so the answer is uniquely determined.

The first line contains two integers $n$ and $k$ separated by a space ($1 \le k \le n \le 300$).

The $i$-th of the next $n$ lines contains one integer $t_i$ ($1 \le t_i \le 10^6$).

Print on one line the sum of the penalties over all read orders, modulo $10^9+7$.