记录编号	236876	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]submultiple	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.408 s
提交时间	2016-03-15 19:23:28	内存使用	0.93 MiB

//出题人强行吧一道题变成三道题。。。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int SIZEN=80000,SIZEK=15,SIZEP=100010;
typedef long long LL;
const LL MOD=1000000007;
int N,K;
LL P[SIZEN];
LL mx=0;
void read()
{
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%lld",&P[i]),mx=max(P[i],mx);
}
LL quickpowint(LL x,int t)
{
	LL re=1;
	while(t)
	{
		if(t&1) re*=x;
		t>>=1;x*=x;
		x%=MOD;re%=MOD;
	}
	return re;
}
void calc3()
{
	LL inv2=quickpowint(2,MOD-2);
	LL ans=1;
	for(int i=1;i<=N;i++)
	{
		LL now=(P[i]+1)%MOD;
		now*=(now+1)%MOD;now%=MOD;
		now*=inv2;now%=MOD;
		now*=now;now%=MOD;
		ans*=now;ans%=MOD;
	}
	printf("%I64d",ans);
}
int C[SIZEK][SIZEK]={0};
class miku
{
public:
	int n,m;
	LL s[SIZEK][SIZEK];
	miku()
	{
		n=m=0;
		memset(s,0,sizeof(s));
	}
	void clear(int a)//成为初始矩阵
	{
		n=m=a;
		for(int i=1;i<=n;i++) s[i][i]=1;
	}
	void lie(int a)//成为列向量
	{
		n=a;m=1;
		for(int i=1;i<=n;i++) s[i][1]=1;
	}
	void make(int a)//成为状态转移矩阵
	{
		n=m=a;
		s[1][1]=1;
		for(int j=2;j<=n;j++) s[1][j]=C[n-2][j-2];
		for(int i=2;i<=n;i++)
		{
			for(int j=i;j<=n;j++) s[i][j]=C[n-i][j-i];
		}
	}
	void print()
	{
		cout<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
};
miku operator *(miku a,miku b)
{
	miku c;
	c.n=a.n;c.m=b.m;
	for(int i=1;i<=c.n;i++)
	{
		for(int j=1;j<=c.m;j++)
		{
			for(int k=1;k<=a.m;k++)
			{
				c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
				c.s[i][j]%=MOD;
			}
		}
	}
	return c;
}
void prepare()
{
	C[0][0]=1;
	for(int i=1;i<=K+1;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
}
miku quickpow(miku x,LL t)
{
	miku re;
	re.clear(K+2);
	while(t)
	{
		if(t&1) re=re*x;
		t>>=1;x=x*x;
	}
	return re;
}
LL calc(LL x)
{
	miku D,A;
	D.make(K+2);
	//D.print();
	A.lie(K+2);
	D=quickpow(D,x);
	//D.print();
	D=D*A;
	return D.s[1][1];
}
void calc_sk()//对于k比较小的情况使用此算法
{
	prepare();
	LL ans=1;
	for(int i=1;i<=N;i++) ans*=calc(P[i]),ans%=MOD;
	printf("%lld\n",ans);
}
void calc_sp()
{
	LL H[SIZEP];
	H[0]=1;
	for(int i=1;i<=mx;i++) H[i]=H[i-1]+quickpowint(i+1,K),H[i]%=MOD;
	LL ans=1;
	for(int i=1;i<=N;i++) ans*=H[P[i]],ans%=MOD;
	printf("%lld\n",ans);
}
void work()
{
	if(K==3) calc3();
	else if(K<=20) calc_sk();
	else calc_sp();
}
int main()
{
	freopen("submultiple.in","r",stdin);
	freopen("submultiple.out","w",stdout);
	read();
	work();
	return 0;
}