대회 전략

프로그래밍 대회에 참가해 문제 $n$개를 모두 풀어야 한다. 문제를 읽는 데 걸리는 시간은 0이고, 한 번 읽으면 그 문제를 푸는 데 걸리는 시간을 정확히 알 수 있다. $i$번 문제를 푸는 데 걸리는 시간은 $t_i$이다.

대회에서 다음 전략을 쓴다.

1. 문제 $k$개를 무작위로 읽는다.
2. 읽었지만 아직 풀지 않은 문제 중에서 푸는 시간이 가장 짧은 문제를 하나 고른다. 가장 짧은 문제가 여럿이면 그중 아무거나 고른다.
3. 그 문제를 풀고, 아직 읽지 않은 문제가 남아 있으면 그중 하나를 무작위로 읽는다.
4. 아직 풀지 않은 문제가 남아 있으면 2번으로 돌아간다.

한 문제의 제출 시각은 그 문제를 다 풀었을 때까지 흐른 시간, 즉 그 문제를 포함해 그때까지 푼 문제의 시간을 모두 더한 값이다. 대회의 페널티는 문제 $n$개의 제출 시각을 모두 더한 값이다.

읽는 순서 하나는 문제 $n$개의 순열 하나에 대응한다. 처음에 순열의 앞 $k$개를 읽고, 한 문제를 풀 때마다 순열의 다음 문제를 읽는다. 페널티는 읽는 순서에 따라 달라지고, 읽는 순서는 $n!$가지이다. 이 $n!$가지 순서의 페널티를 모두 더한 값을 $10^9+7$로 나눈 나머지를 구하여라.

2번에서 시간이 가장 짧은 문제가 여럿일 때 어느 것을 고르든 페널티는 같으므로, 답은 하나로 정해진다.

첫째 줄에 정수 $n$과 $k$가 공백을 사이에 두고 주어진다. ($1 \le k \le n \le 300$)

다음 $n$개 줄 중 $i$번째 줄에 정수 $t_i$가 주어진다. ($1 \le t_i \le 10^6$)

모든 읽는 순서에 대한 페널티의 합을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.