Yooglex 公司有 $n$ 名员工。第 $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$。这类员工 $j$ 的数量即为员工 $i$ 的得分。

董事会决定，尝试在两种方法中做出选择是徒劳的，因此建议采用第三种方法，即上述两种方法所得分数的乘积。

你能足够快地计算出第三种评估方法的得分吗？

输入格式

输入的第一行包含两个整数 $n$ 和 $k$：员工人数和大厅容量（$1 \le n \le 300$，$1 \le k \le n$）。 第二行包含 $n$ 个整数 $t_1, \dots, t_n$：每名员工的工作量（$1 \le t_i \le 10^9$）。所有 $t_i$ 均不相同。

输出格式

输出 $n$ 个整数：员工的评估得分，顺序与输入中的工作量顺序一致。由于得分可能非常大，请输出它们对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3 1
2 1 3

样例输出 1

72 126 0

样例输入 2

4 2
10 30 2 7

样例输出 2

0 0 3564 2208