Little relyt871 有一台神奇的机器。在每一次操作中，他的机器可以对输入数组 $b$ 执行以下两种操作之一：

• 生成 $b$ 的一个副本并将其连接在 $b$ 之后。更正式地说，结果数组应为 $b' = \{b_1, b_2, \dots, b_{|b|}, b_1, b_2, \dots, b_{|b|}\}$。
• 生成 $b$ 的一个副本，将其反转，然后连接在 $b$ 之前。更正式地说，结果数组应为 $b' = \{b_{|b|}, b_{|b-1|}, \dots, b_1, b_1, b_2, \dots, b_{|b|}\}$。

最初，他有一个长度为 $n$ 的数组 $a$。他想要使用手中的数组精确地操作机器 $m$ 次，同时最大化最终数组的所有前缀和之和。由于他的脑容量有限，在进行加法运算时，他只关心模 $1\,000\,000\,007$ 后的结果。形式化地，假设在所有 $m$ 次操作后，他得到了长度为 $n'$ 的数组 $b$，他想要最大化以下值：

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

请注意，你应该在取模后最大化该值：在取模前结果为 $1\,000\,000\,007$ 的数组被认为小于结果为 $1$ 的数组。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，以空格分隔。

输出格式

输出一行，包含一个整数，表示答案。

样例

输入 1

2 1
1 2

输出 1

15

输入 2

5 10
26463 39326 86411 75307 85926

输出 2

806275469