#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define maxn 111111
#define LL long long
#define Matr 10
#define MOD  10000007
int num[maxn];
struct mat
{
    LL a[Matr][Matr],size;
    mat()
    {
        size=0;
        memset(a,0,sizeof(a));
    }
};
mat multi(mat m1,mat m2,int mod)//两个相等矩阵的乘法，对于稀疏矩阵，有0处不用运算的优化 
{
    mat ans=mat();    ans.size=m1.size;
    for(int i=1;i<=m1.size;i++)
        for(int j=1;j<=m2.size;j++)
            if(m1.a[i][j])//稀疏矩阵优化 
                for(int k=1;k<=m1.size;k++)
                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%mod;

    return ans;
}
mat quickmulti(mat m,int n,int mod)//二分快速幂 
{
    mat ans=mat();
    int i;
    for(i=1;i<=m.size;i++)ans.a[i][i]=1;
    ans.size=m.size;
    while(n)
    {
        if(n&1)ans=multi(m,ans,mod);
        m=multi(m,m,mod);
        n>>=1;
    }
    return ans;
}
void debug(mat a)
{
    int i, j;
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++) printf("%I64d ",a.a[i][j]);
        printf("\n");
    }
    printf("\n");
}
int main()
{
    int n, k, i;
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        int aaa;
        LL sum  = 0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
            sum+=num[i]%MOD;
        }
        sort(num,num+n);
        mat x;
        x.size = 3;
        x.a[1][1]  = 2;
        x.a[1][2]  = 0;
        x.a[1][3]  =  -1; 
        x.a[2][1]  = 1;
        x.a[2][2]  =  0;
        x.a[2][3] = 0;
        x.a[3][1]  = 0;
        x.a[3][2]  =  1;
        x.a[3][3] = 0;
        mat y ;
        y.size = 3;
        
        y.a[1][1] = num[n-1]+num[n-2];
        y.a[2][1] = y.a[1][1]+y.a[1][1]+num[n-1];
        y.a[3][1] = y.a[2][1]+y.a[2][1];
        y.a[1][2]  = y.a[1][3]  = y.a[2][2] = y.a[2][3] = y.a[3][2] = y.a[3][3] = 0;
        if(k<=3)
        {
            printf("%I64d\n",(sum+y.a[k][1])%MOD);
        }
        else
        {
              int a = y.a[1][1],b  = y.a[2][1],c = y.a[3][1];
             y.a[1][1] = c,y.a[3][1] = a;
             x = quickmulti(x,k-3,MOD);
        //     debug(y);
            // debug(x);
                y = multi(x,y,MOD);
               // debug(y);
                printf("%I64d\n",(sum+y.a[1][1])%MOD);
        }
        
    }
    return 0;
}