Little Yuuka encountered a problem: there is a sequence $a_1, a_2, \dots, a_n$ and $q$ operations. Each operation changes the numbers in a range to the maximum value within that range. The question is what each number becomes at the end. Little Yuuka quickly solved this problem using a segment tree.

Being a wise girl, Little Yuuka wondered: if the operations are random, i.e., in each of the $q$ operations, we choose a range $[l, r]$ ($1 \le l \le r \le n$) uniformly at random (note that there are $\frac{n(n+1)}{2}$ such ranges) and change the numbers in this range to the maximum value within it, what is the expected value of each number at the end?

Little Yuuka loves randomness, so the input sequence she provides is also random (see Constraints for the generation method).

For each number, output its expected value multiplied by $\left(\frac{n(n+1)}{2}\right)^q$ modulo $10^9 + 7$.

Input

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

The next line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$.

Output

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

Examples

Input 1

5 5
1 5 2 3 4

Output 1

3152671 3796875 3692207 3623487 3515626

Input 2

See segment/segment_ex1.in in the contestant directory.

Output 2

See segment/segment_ex1.ans in the contestant directory.

Note

Sample inputs and outputs 1 and 2 do not satisfy the generation method described in the constraints.

Input 3

See segment/segment_ex2.in in the contestant directory.

Output 3

See segment/segment_ex2.ans in the contestant directory.

Constraints

For all test data, it is guaranteed that the values in the sequence do not exceed $10^9$, i.e., $a_i \le 10^9$, and each number is a random integer between $0$ and $10^9$.

Each test case satisfies the following constraints: