题意：

开始时集合中有n个数。

现在要进行k次操作。

每次操作：从集合中挑最大的两个数a,b进行相加，得到的数添加进集合中。

以此反复k次。

问最后集合中所有数的和是多少。

(2≤n≤100000,1≤k≤1000000000)

思路：

写出来发现是要求Fibonaci的前n个数的和。

Fibonaci是用矩阵快速幂求的，这个也可以。

[Sn,Fn,Fn-1]=[某个矩阵]*[Sn-1,Fn-1,Fn-2]

[S2,F2,F1]=[2,1,1]

然后写，，，

这个代码有些繁琐，应该把矩阵操作单独写成函数。

日后更新。

代码：

ll const mol = 10000007;

int n,k;
ll ans;
ll matrix[4][4];
int a[100005];

void matrixSolve(int k){ // ¾ØÕóµÄk´Î·½
if(k==0){
mem(matrix,0);
matrix[1][1]=1;
matrix[2][2]=1;
matrix[3][3]=1;
return;
}
if(k==1){
mem(matrix,0);
matrix[1][1]=matrix[1][2]=matrix[1][3]=1;
matrix[2][2]=matrix[2][3]=1;
matrix[3][2]=1;
return;
}
matrixSolve(k/2);
ll tempMatrix[4][4];
mem(tempMatrix,0);
rep(i,1,3){
rep(j,1,3){
rep(k,1,3){
tempMatrix[i][j]=(tempMatrix[i][j]+matrix[i][k]*matrix[k][j]%mol)%mol;
}
}
}
rep(i,1,3){
rep(j,1,3){
matrix[i][j]=tempMatrix[i][j];
}
}
if((k&1)==1){
ll temp2Matrix[4][4];
mem(temp2Matrix,0);
temp2Matrix[1][1]=temp2Matrix[1][2]=temp2Matrix[1][3]=1;
temp2Matrix[2][2]=temp2Matrix[2][3]=1;
temp2Matrix[3][2]=1;

    ll temp3Matrix\[4\]\[4\];  
    mem(temp3Matrix,0);  
    rep(i,1,3){  
        rep(j,1,3){  
            rep(k,1,3){  
                temp3Matrix\[i\]\[j\]=(temp3Matrix\[i\]\[j\]+tempMatrix\[i\]\[k\]\*temp2Matrix\[k\]\[j\])%mol;  
            }  
        }  
    }  
    rep(i,1,3){  
        rep(j,1,3){  
            matrix\[i\]\[j\]=temp3Matrix\[i\]\[j\];  
        }  
    }  
}

}

ll solve(int k){ //calc Sk
ll s2=2,f2=1,f1=1;
matrixSolve(k-2);
ll sk=(matrix[1][1]*s2+matrix[1][2]*f2+matrix[1][3]*f1)%mol;
return sk;
}

int main(){

while(cin>>n>>k){  
    ans=0;  
    rep(i,1,n){  
        scanf("%d",&a\[i\]);  
        ans=(ans+a\[i\])%mol;  
    }  
    sort(a+1,a+1+n);  
    if(k==1){  
       ans=(ans+a\[n-1\])%mol;  
       ans=(ans+a\[n\])%mol;  
       printf("%I64d\\n",ans);  
    }  
    else{  
        int xx=a\[n-1\];  
        int yy=a\[n\];  
        ll ans1=(solve(k)\*(ll)xx)%mol;  
        ll ans2=((solve(k+1)-1)\*(ll)yy)%mol;  
        ans=(ans+ans1+ans2)%mol;  
        printf("%I64d\\n",ans);  
    }  
}

return 0;  

}