由于 PJudge 的题面没有主线故事，鱼王青鱼买了一台造题面机。

题面可以抽象成一个正整数序列。造题面机每次可以对输入的序列 $b$ 进行两种操作之一：

• 输入序列 $b$ ，返回 $\{b_1,b_2,\cdots,b_{|b|},b_1,b_2,\cdots,b_{|b|}\}$ ，即将 $b$ 复制一份并接在前面。
• 输入序列 $b$ ，返回 $\{b_{|b|},\cdots,b_{2},b_1,b_1,b_2,\cdots,b_{|b|}\}$ ，即将 $b$ 复制一份、翻转、接在前面。

青鱼有一个长度为 $n$ 的正整数序列 $a$ 。青鱼希望题面的长度是 $2^mn$，于是她用造题面机对 $a$ 进行 $m$ 次操作。

青鱼有奇怪的审美。设最终得到的序列为 $b$ ，其长度为 $n'$ ，则青鱼希望最大化

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

但是鱼的记忆力只有七秒，所以青鱼无法算出上式的准确值。她转而希望最大化上式模 $10^9+7$ 的值（注意是求取模之后的最大值），即最大化

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

请帮青鱼求出上式的最大值。

输入格式

第一行两个正整数 $n,m$ ,分别表示序列长度和操作次数。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 。

输出格式

输出一行一个非负整数，表示答案。

样例

样例输入 1

2 1
1 2

样例输出 1

15

样例 1 解释

青鱼选择第二种操作，将 $\{1,2\}$ 变成 $\{2,1,1,2\}$ 。计算得到此时的值为 $15$ 。

样例输入 2

5 10
26463 39326 86411 75307 85926

样例输出 2

806275469

数据范围

本题采用捆绑测试，你需要通过一个子任务的所有测试点才能得到子任务的分数。

对于所有测试点，$1\le n,m\le 10^5,1\le a_i\le 10^9$ 。详细数据范围如下表。