记录编号	142325	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]submultiple	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.065 s
提交时间	2014-12-07 18:06:41	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const int SIZEK=15,SIZE=100010;
class MATRIX{
public:
	int n,m;
	LL s[SIZEK][SIZEK];
	void clear(int n_,int m_){
		n=n_,m=m_;
		memset(s,0,sizeof(s));
	}
	void clear_identity(int n_){
		clear(n_,n_);
		for(int i=0;i<n_;i++) s[i][i]=1;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.n=a.n,c.m=b.m;
	for(int i=0;i<c.n;i++){
		for(int j=0;j<c.m;j++){
			c.s[i][j]=0;
			for(int k=0;k<a.m;k++){
				c.s[i][j]+=a.s[i][k]*b.s[k][j];
				c.s[i][j]%=MOD;
			}
		}
	}
	return c;
}
MATRIX quickpow(MATRIX a,LL n){
	MATRIX ans;
	ans.clear_identity(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
LL C[SIZEK][SIZEK]={0};
void prepare_C(void){//递推组合数
	for(int i=0;i<SIZEK;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
}
int N,K;
LL P[SIZE]={0};
MATRIX D;
LL calc(LL p){//1^K+2^K+...+(p+1)^K
	MATRIX O;
	O.clear(1,K+2);
	for(int i=0;i<=K;i++) O.s[0][i]=1;
	O=O*quickpow(D,p+1);
	return O.s[0][K+1];
}
void prepare_D(void){//递推转移矩阵
	D.clear(K+2,K+2);
	//位置0~K是0次方~K次方,位置K+1是和
	for(int i=0;i<=K;i++)
		for(int j=i;j<=K;j++)
			D.s[i][j]=C[j][i];
	D.s[K][K+1]=D.s[K+1][K+1]=1;
}
void small_K_work(void){
	prepare_C();
	prepare_D();
	LL ans=1;
	for(int i=1;i<=N;i++) ans=(ans*calc(P[i]))%MOD;
	printf("%lld\n",ans);
}
LL f[SIZE]={0};
void small_P_work(void){
	f[0]=0;
	for(int i=1;i<SIZE;i++) f[i]=(f[i-1]+quickpow(i,K))%MOD;
	LL ans=1;
	for(int i=1;i<=N;i++) ans=(ans*f[P[i]+1])%MOD;
	printf("%lld\n",ans);
}
void K_3_work(void){
	LL ans=1,inv2=quickpow(2,MOD-2);
	for(int i=1;i<=N;i++){
		LL now=(P[i]+1)%MOD;
		now*=(P[i]+2)%MOD;now%=MOD;
		now*=inv2;now%=MOD;
		ans*=(now*now)%MOD;
		ans%=MOD;
	}
	printf("%lld\n",ans);
}
void read(void){
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%lld",&P[i]);
}
int main(){
	freopen("submultiple.in","r",stdin);
	freopen("submultiple.out","w",stdout);
	read();
	if(K==3) K_3_work();
	else if(K<=12) small_K_work();
	else small_P_work();
	return 0;
}