Since PJudge problem statements lack a main storyline, the fish king Qingyu bought a problem statement generator.

A problem statement can be abstracted as a sequence of positive integers. The generator can perform one of two operations on an input sequence $b$:

• Input sequence $b$, return $\{b_1,b_2,\cdots,b_{|b|},b_1,b_2,\cdots,b_{|b|}\}$, which is $b$ concatenated with a copy of itself.
• Input sequence $b$, return $\{b_{|b|},\cdots,b_{2},b_1,b_1,b_2,\cdots,b_{|b|}\}$, which is $b$ reversed and concatenated with $b$.

Qingyu has a sequence $a$ of $n$ positive integers. Qingyu wants the length of the problem statement to be $2^m n$, so she performs $m$ operations on $a$ using the generator.

Qingyu has strange aesthetic tastes. Let the final sequence be $b$ with length $n'$. Qingyu wants to maximize

$$ \sum_{i=1}^{n'}\sum_{j=1}^i b_j $$

However, a fish's memory only lasts seven seconds, so Qingyu cannot calculate the exact value of the above expression. Instead, she wants to maximize the value of the expression modulo $10^9+7$ (note that this is the maximum value after taking the modulo), i.e., maximize

$$ \left(\sum_{i=1}^{n'}\sum_{j=1}^i b_j\right)\bmod {1\,000\,000\,007} $$

Please help Qingyu find the maximum value of the above expression.

Input

The first line contains two positive integers $n$ and $m$, representing the sequence length and the number of operations, respectively.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$.

Output

Output a single non-negative integer representing the answer.

Examples

Input 1

2 1
1 2

Output 1

15

Note 1

Qingyu chooses the second operation, turning $\{1,2\}$ into $\{2,1,1,2\}$. The calculated value is $15$.

Input 2

5 10
26463 39326 86411 75307 85926

Output 2

806275469

Constraints

This problem uses bundled testing; you must pass all test cases in a subtask to receive the points for that subtask.

For all test cases, $1\le n,m\le 10^5, 1\le a_i\le 10^9$. The detailed constraints are as follows: