Employees

There are $n$ employees in the company Yooglex. The $i$-th employee has to work $t_i$ time units per day. These values are different for all employees. Yooglex's work process is unusual: at every moment only one employee can work, and the rest have to wait until that employee is done.

The Yooglex office consists of a hall and a room. No more than $k$ employees can be in the hall at the same time. Employees form a queue outside the office to enter the hall. Then the following algorithm applies:

1. While there are fewer than $k$ employees in the hall and at least one employee in the queue, the front employee of the queue enters the hall.
2. If the hall is empty, the day is over and the room is locked.
3. The employees in the hall choose the one among themselves whose workload for the day is minimal.
4. The chosen employee enters the room, works for their time, and leaves the office for the day.
5. Go back to step 1.

The Yooglex board wants to evaluate its employees to assign sensible salaries. Two evaluation methods have been proposed.

The first one is simple. For each of the $n!$ possible permutations of the employee queue and each employee $i$, calculate the time between the moment the first employee in the queue enters the room and the moment employee $i$ leaves the room. For each employee, sum these times over all $n!$ queue permutations. The sums are the final scores.

The second method is even simpler. For the $i$-th employee and each queue permutation, count all employees $j$ such that $t_j > t_i$ but employee $j$ finishes the job before employee $i$. This count is the score for employee $i$.

Choosing between the two methods is pointless, so a third method is proposed: the score of each employee is the product of the scores from the first two methods.

Can you calculate the third method's scores quickly enough?

The first line contains two integers $n$ and $k$: the number of employees and the hall capacity ($1 \le n \le 300$, $1 \le k \le n$).

The second line contains $n$ integers $t_1, \ldots, t_n$: the workloads of the employees ($1 \le t_i \le 10^9$). All $t_i$ are different.

Output $n$ integers: the evaluation scores of the employees, in the same order as their workloads in the input. Since the scores can be very large, output them modulo $10^9 + 7$.