1946: 耐久魔法

林克背着一排武器。每件武器都有各自的耐久度，在战斗中会逐渐损耗。

有一天，海拉鲁的女神给了林克一个神秘的“强化试炼”—— 每次试炼，林克都会随机选择一段连续的武器（编号为 [l,r]），并用其中最结实的一把来强化整个区间，使得这段区间内所有武器的耐久都变成该区间的最大耐久值。

林克非常喜欢这种随机又强力的强化，于是他决定重复这种操作共 q 次。

林克的背包中共有 n 把武器，初始耐久分别为 a1, a2, ..., an。 在进行 q 次随机强化操作后，林克想知道每一把武器的期望耐久度是多少。

由于期望可能是分数，林克希望输出：

Ei × ( n(n + 1) / 2 )q mod (109 + 7)

其中 Ei 表示第 i 把武器的期望耐久度。

输入共两行：

• 第一行包含两个正整数 n, q，分别表示武器的数量和强化试炼的次数。
• 第二行包含 n 个非负整数 a1, a2, ..., an，表示每把武器的初始耐久度。

输出一行，包含 n 个整数，第 i 个数表示第 i 把武器的答案，即期望耐久度乘上 ( n(n + 1) / 2 )q 并对 109 + 7 取模的结果。

5 5
1 5 2 3 4

3152671 3796875 3692207 3623487 3515626