직원 평가

Yooglex 회사에는 직원이 $n$명 있다. $i$번째 직원은 하루에 $t_i$ 단위 시간만큼 일해야 한다. 모든 직원의 $t_i$ 값은 서로 다르다. Yooglex의 업무 방식은 특이하다. 어느 순간에도 한 명만 일할 수 있고, 나머지는 그 직원이 끝날 때까지 기다려야 한다.

Yooglex 사무실은 대기실과 방으로 이루어져 있다. 대기실에는 동시에 $k$명을 넘을 수 없다. 직원들은 사무실 밖에서 줄을 서서 대기실에 들어간다. 이후 다음 알고리즘이 적용된다.

1. 대기실에 있는 직원이 $k$명 미만이고 줄에 직원이 한 명 이상 남아 있는 동안, 줄 맨 앞의 직원이 대기실에 들어간다.
2. 대기실이 비어 있으면 그날 업무는 끝나고 방은 잠긴다.
3. 대기실의 직원들 가운데 그날 업무량이 가장 적은 직원을 고른다.
4. 선택된 직원이 방에 들어가 자기 시간만큼 일하고, 그날 사무실을 떠난다.
5. 1단계로 돌아간다.

Yooglex 이사회는 적절한 급여를 정하기 위해 직원을 평가하려 한다. 평가 방법 두 가지가 제안되었다.

첫 번째 방법은 간단하다. 직원 줄의 가능한 순열 $n!$개 각각에 대해, 그리고 직원 $i$마다, 줄 맨 앞의 직원이 방에 들어간 순간부터 직원 $i$가 방에서 나간 순간까지의 시간을 구한다. 각 직원에 대해 이 시간들을 $n!$개 순열 전체에 걸쳐 더한다. 그 합이 최종 점수이다.

두 번째 방법은 더 간단하다. $i$번째 직원과 각 줄 순열에 대해, $t_j > t_i$이면서 직원 $j$가 직원 $i$보다 먼저 업무를 끝내는 직원 $j$를 모두 센다. 그 개수가 직원 $i$의 점수이다.

두 방법 중 하나를 고르는 것은 의미가 없으므로, 세 번째 방법이 제안되었다. 각 직원의 점수는 앞의 두 방법으로 얻은 점수를 곱한 값이다.

세 번째 방법의 점수를 충분히 빠르게 계산할 수 있는가?

첫 줄에는 직원 수 $n$과 대기실 수용 인원 $k$가 주어진다 ($1 \le n \le 300$, $1 \le k \le n$).

둘째 줄에는 각 직원의 업무량 $t_1, \ldots, t_n$이 주어진다 ($1 \le t_i \le 10^9$). 모든 $t_i$는 서로 다르다.

$n$개의 정수를 출력한다. 각 정수는 입력에서의 순서대로 직원의 평가 점수이다. 점수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.