#include<bits/stdc++.h>

 using namespace std;

 #define fu(a,b,c) for(int a=b;a<=c;++a)

 #define N 100010

 #define INF 0x3f3f3f3f

 #define LL long long

 #define Mod 10000007

 struct Matrix{LL t[][];};

 Matrix mul(Matrix a,Matrix b){

   Matrix c;

   memset(c.t,,sizeof(c.t));

   fu(i,,)fu(j,,)fu(k,,)

     c.t[i][j]=(c.t[i][j]+a.t[i][k]*b.t[k][j]%Mod+Mod)%Mod;

   return c;

 }

 Matrix fast_pow(Matrix a,LL b){

   Matrix ans;

   fu(i,,)fu(j,,)ans.t[i][j]=(i==j);

   while(b){

     if(b&)ans=mul(ans,a);

     a=mul(a,a);

     b>>=;

   }

   return ans;

 }

 int solve(LL max1,LL max2,LL k){

   Matrix tmp,ans;

   tmp.t[][]=;tmp.t[][]=;tmp.t[][]=;

   tmp.t[][]=;tmp.t[][]=;tmp.t[][]=;

   tmp.t[][]=;tmp.t[][]=;tmp.t[][]=;

   tmp=fast_pow(tmp,k);

   ans.t[][]=max1;ans.t[][]=max2;ans.t[][]=;

   ans.t[][]=;ans.t[][]=;ans.t[][]=;

   ans.t[][]=;ans.t[][]=;ans.t[][]=;

   ans=mul(ans,tmp);

   return ans.t[][];

 }

 int main(){

   LL n,k,sum=,max1=-INF,max2=-INF;

   scanf("%lld%lld",&n,&k);

   fu(i,,n){

     LL x;scanf("%lld",&x);

     sum=(sum+x%Mod+Mod)%Mod;

     if(x>max1)max2=max1,max1=x;

     else if(x>max2)max2=x;

   }

   if(max1>&&max2>)printf("%lld",(sum+solve(max1,max2,k)+Mod)%Mod);

   else if(max1<&&max2<)printf("%lld",(sum+(max1+max2)*k%Mod+Mod)%Mod);

   else{

     int cnt=;

     while(max2<){

       int newv=max1+max2;

       if(newv>max1){max2=max1,max1=newv;}

       else{max2=newv;}

       sum=(sum+newv)%Mod;

       cnt++;

       if(cnt==k)break;

     }

     if(cnt==k)printf("%lld",(sum+Mod)%Mod);

     else printf("%lld",(sum+solve(max1,max2,k-cnt)+Mod)%Mod);

   }

   return ;

 }