Description

Little Yuuka encountered a problem: given a sequence $a_1, a_2, \ldots, a_n$ and $q$ operations. In each operation, choose an interval $[l, r]$ and set all numbers in that interval to the maximum value within the interval. After all operations, what is the final value of each number? Little Yuuka quickly solved this using a segment tree.

Then the wise Little Yuuka wondered: what if the operations are random? That is, in each of the $q$ operations, we choose an interval $[l, r]$ uniformly at random among all intervals with $1 \leq l \leq r \leq n$, and then set all numbers in that interval to the interval maximum (note that there are $\frac{n(n+1)}{2}$ such intervals). What is the expected final value of each number?

Little Yuuka loves randomness, so the input sequence is also random (see Constraints and conventions in the Hint).

For each position, output its expectation multiplied by $\left(\frac{n(n+1)}{2} \right)^q$, then taken modulo $10^9+7$.

Input Format

The first line contains two positive integers $n, q$, the number of elements in the sequence and the number of operations.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$.

Output Format

Output a single line containing $n$ integers, the answer for each position.

5 5
1 5 2 3 4

3152671 3796875 3692207 3623487 3515626

Hint

For all testdata, the values in the sequence are at most $10^9$, and each number is a random integer between $0$ and $10^9$.

Translated by ChatGPT 5