/*****************************************
Note：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e7 + 10;
const int mod = 1e7 + 7;
int n  , a[N] , sum =0 , k;
struct node
{
	int s[4][4];
	node ()
	{
		memset(s,0 , sizeof s);
	}
}num , ans;
node operator * (const node a , const node b)
{
	node z;
	for(int i = 0 ; i < 3 ; i++)
		for(int j = 0 ; j < 3 ; j++)
			for(int k = 0 ; k < 3 ; k++)
				z.s[i][j] = (z.s[i][j] + a.s[i][k] * b.s[k][j]) % mod;
	return z;
}
void calc(int p)
{
	ans.s[0][0] = ans.s[1][1] = ans.s[2][2] = 1;
	while(p)
	{
		if(p&1)
			ans = ans * num;
		p >>= 1;
		num = num * num;
	}
}
signed main()
{
	cin >> n >> k;
	for(int i = 0; i < n ; i++)
	{
		scanf("%lld", &a[i]);
		sum = (sum + a[i])%mod;
	}
	sort(a,a+n);
	int a1 = a[n-1] , a2 = a[n-2];
	if(a2 < 0)
	{
		int l = ceil(fabs(a2)/a1);
		sum = (sum +  (a2 + a1 + a2 + a1 * l)*(l)/2 )%mod;
		a2 = a2 + a1*l;
		k-= l;
	}
	a1 %= mod , a2 %= mod;
	num.s[1][1] = num.s[0][0] = num.s[1][2] = num.s[1][0] = num.s[2][1] = num.s[2][0] = 1;
	calc(k);
	sum = (ans.s[0][0] * sum + ans.s[1][0] * a1 + ans.s[2][0] * a2) % mod;
	cout << sum << endl;
	return 0;
}