Random Interval Maximum Propagation

You are given a sequence \(a_1,a_2,\dots,a_n\) and an integer \(q\). In each of the \(q\) operations, a random interval \([l,r]\) (with \(1\le l\le r\le n\)) is chosen uniformly among all \(\frac{n(n+1)}{2}\) possible intervals, and then every number in that interval is replaced by the maximum value in that interval.

Let \(T=\frac{n(n+1)}{2}\). After performing all \(q\) operations (the operations are performed independently), for each position \(i\) you are asked to output the expected final value of \(a_i\) multiplied by \(T^q\) modulo \(10^9+7\). All formulas should appear in LaTeX format.

Note: In this version of the problem, you may assume that \(q\) is either 0 or 1.

Example explanation for \(q=1\):

When \(q=1\), one operation is performed. For any index \(i\), if the chosen interval does not cover \(i\) then \(a_i\) remains unchanged; otherwise, if the chosen interval is \([l,r]\) with \(l\le i\le r\), then the new value at \(i\) becomes \(\max\{a_l, a_{l+1}, \dots, a_r\}\). Since each interval is chosen uniformly, the probability that index \(i\) is covered is \(\frac{i\cdot (n-i+1)}{T}\) (because there are exactly \(i\cdot (n-i+1)\) intervals that cover position \(i\)). Thus, the expected final value at position \(i\) is \[ E[a_i] = \left(1-\frac{i\cdot (n-i+1)}{T}\right)a_i + \frac{1}{T}\sum_{l=1}^{i}\sum_{r=i}^{n} \max\{a_l,a_{l+1},\dots,a_r\}. \] The answer to output is \(E[a_i] \cdot T\) modulo \(10^9+7\) (note that in the general problem it is multiplied by \(T^q\), here \(q=1\)).

inputFormat

The first line contains two integers \(n\) and \(q\) (with \(1\le n\le 50\) and \(q\) is either 0 or 1).

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output \(n\) integers separated by spaces, where the \(i\)th integer is the expected final value of \(a_i\) multiplied by \(T^q\) (with \(T=\frac{n(n+1)}{2}\)) modulo \(10^9+7\).

sample

2 1
1 2

4 6