由于 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$ 。详细数据范围如下表。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $n\le 10,m\le 5$ | $20$ |
| $2$ | $n\le 50,m\le 10$ | $20$ |
| $3$ | $a_i=a_{n-i+1}$ | $30$ |
| $4$ | 无 | $30$ |