Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓
统计

由于 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$