题目描述

你有一个由 $n$ 个整数组成的数组 $a$ 。

你要对它进行 $k$ 次操作。其中一个操作是选择数组 $a$ 的任意连续子数组(可能为空)，并在数组的任意位置插入该子数组的和。

你的任务是找出 $k$ 次这样的操作后数组可能的最大和。

由于这个数字可能非常大，请输出取模为 $10^9+7$ 的答案。

提示：数字 $x\mod\ p$ 的余数等于最小非负数 $y$，满足 $x=p*q+y$ ($q$ 为整数)。

输入格式

第一行包含两个整数 $n$ 和 $k(1 \leq n,k \leq 2*10^5)$---分别是数组的长度 $a$ 和操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(-10^9 \leq a_i \leq 10^9)$。

输出格式

输出一个整数---经过 $k$ 次运算模数 $10^9+7$ 后得到的数组最大和。

样例

样例输入 #1

2 2
-4 -7

样例输出 #1

999999996

样例输入 #2

3 3
2 2 8

样例输出 #2

96

提示

样例解释 $1$: 在第一个测试用例中，最好在数组中取一个空子数组两次，并在任意位置插入空子数组的和$(0)$，这样得到的数组和为 $(-4)+(-7)+0+0=-11$，模数 $10^9+7$ 为 $999999996$。