矩阵快速幂，开始没看出来以为是杨辉三角，后来t了一发想到ON并不能过，一开始矩阵推不出来，顾分开考虑，输入的n部分依旧按组合数学来做，233部分使用矩阵快速幂，关系变显然得知。
以后要多注意有线性递推关系但n过大的题联想矩阵快速幂，另外矩阵快速幂似乎还有别的用途，碰到来填坑
| 1 0 0 0 ...|
| 1 10 1 0 ...|
| 1 10 1 1 ...|
| 1 10 1 1 1..|
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int mo=1e7+7;
int n,m;
typedef vector<vector<long long> > mat;
typedef long long LL;
mat mul(mat &A, mat &B)
{
mat C(A.size(),vector<long long>(B[0].size()));
for(int i = 0; i < A.size(); i++)
for(int k = 0; k < B.size(); k++)
for(int j = 0; j < B[0].size(); j++)
{
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mo;
}
return C;
}
mat pow(mat A, LL n,mat B)
{
while(n>0)
{
if(n & 1) B =mul(A,B);
A = mul(A,A);
n >>= 1;
}
return B;
}
void gcd(long long a,long long b,int &d,int &x,int &y){
if(!b){d=a;x=1;y=0;}
else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
long long mod_r(long long b,long long p){
int x,y,d;
gcd(b,p,d,x,y);
if(d!=1) return -1;
return (x%p+p+p)%p;
}
long long C(int nn,int mm){
long long ret=1;
if(mm==0||mm==nn)
return ret;
for(int i=nn-mm+1;i<=nn;i++){
ret=(ret*i)%mo;
}
for(int i=2;i<=mm;i++){
ret=(ret*mod_r(i,mo))%mo;
}
return ret;
}
int main()
{
while(~scanf("%d%d",&m,&n)){
long long ans=0;
int x;
long long to=233;
for(int i=1;i<=m;i++){
scanf("%d",&x);
ans=(ans+(C(n-1+m-i,m-i)*x)%mo)%mo;
}
mat AA,BB;
vector<long long>q;
for(int i=0;i<=m+1;i++){
AA.push_back(q);
for(int j=0;j<=m+1;j++){
AA[i].push_back(0);
}
}
for(int i=0;i<=m+1;i++){
for(int j=0;j<=m+1;j++){
if(i>0&&j==1)
AA[i][j]=10;
else if(j<=i)
AA[i][j]=1;
}
}
for(int i=0;i<=m+1;i++){
BB.push_back(q);
BB[i].push_back(233);
}
BB[0][0]=3;
BB=pow(AA,n-1,BB);
ans+=BB[m+1][0];
cout<<(ans+mo)%mo<<endl;
}
return 0;
}