T351561 [CZOI Online #4] 序列

给定一个长度为 $n$ 的序列。接下来你可以对这个序列进行 $m$ 次操作， 对于一个序列，每次可以进行两种操作之一： * 输入序列 $b$ ，返回 $\{b_1, b_2, ..., b_{|b|}, b_1, b_2, ..., b_{|b|}\}$，即将 $b$ 复制一份并接在前面。 * 输入序列 $b$ ，返回 $\{b_{|b|}, ..., b_2, b_1, b_1, b_2, ..., b_{|b|}\}$，即将 $b$ 复制一份、翻转、接在前面。 有一个长度为 $n$ 的正整数序列 $a$。为了得到一个长度为 $2^mn$ 的序列，你需要对原始的序列 $a$ 进行 $m$ 次操作。 设最终得到序列为$b$，你需要最大化下面这个式子： $$(\sum_{i=1}^{2^mn} \sum_{j=1}^{i} b_j) \bmod (10^9+7)$$ 求出上述式子的最大值（注意是求取模之后的最大值）。

第一行有两个整数 $n$，$m$，分别表示序列的长度和操作次数。 第二行 $n$ 个正整数 $a_1,a_2,...,a_n$。

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

**样例#1解释** 你选择第二种操作，将 $\{1,2\}$ 变为 $\{2,1,1,2\}$。计算得到此时的值为 $15$。 **数据范围及约定** 本题采用捆绑测试。对于每个 subtask，你需要通过其中所有的测试点之后才可以得到该 subtask 的分数。 对于所有测试点都有 $1\le n,m \le 10^5,1\le a_i \le 10^9$。 **subtask0(20pts)** 特殊性质：$n\le 10,m\le 5$。 **subtask1(20pts)** 特殊性质：$n\le 50,m\le 10$。 **subtask2(30pts)** 特殊性质：$a_i = a_{n-i+1}$。 **subtask3(30pts)** 没有特殊性质。