题目描述

hke有一天学会了循环语句，感到很神奇。回到家，他用c++写下这段代码： 

void work()
{
  ans=0;
    for(a[1]=1;a[1]<=n;++a[1])
      for(a[2]=1;a[2]<a[1];++a[2])
        for(a[3]=1;a[3]<a[2];++a[3])
          //......
            for(a[k]=1;a[k]<a[k-1];++a[k])
              ans+=f(q);
 cout<<ans;
}

其中，qq是给定的常数，f(x)f(x)是一个关于xx的mm次多项式，它的表达式为： 

hke迫不及待地开始运行这个程序，但程序运行得实在太慢了。于是他找到了你，想知道这段程序输出的结果是？答案可能很大，你只需输出其对10^9+7109+7取模的结果即可。假设运算过程中不存在溢出。

输入格式

第一行4个正整数，分别为n,m,k,qn,m,k,q；

第二行m+1个正整数，分别为a_0,a_1,a_2\cdots a_ma0,a1,a2⋯am；

输出格式

一个数，表示程序运行结果对10^9+7109+7取模的结果。

输入输出样例

输入 #1复制 
10 3 3 2
1 3 3 1
输出 #1复制 
3240

说明/提示

10%的数据有n≤10；

30%的数据有n≤1000，m≤1000；

100%的数据保证n≤500000，m≤500000，1≤k≤n，q≤10^18，1≤bi≤10000。



题解：
ans=循环次数*f
①循环次数：题目设定就相当于在n个数中去k个，因为这k个数的顺序是固定的，所以是k个数顺序唯一的
    即C（n，k）因为mod是素数所以用费马小定理
②f计算：多项式计算老方法 
#include <bits/stdc++.h>

using namespace std;
const int N=5e5+10, mod=1e9+7;
typedef long long ll;

ll n,m,q,k,ans,f;
ll fact[N],a[N];

ll qmi(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		b>>=1; a=a*a%mod;
	}
	return ans;
}
int main(int argc, char** argv) {
	cin>>n>>m>>k>>q;
	q%=mod;
	for(int i=0;i<=m;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=m;i>=0;i--){
		f=((f*q%mod)+a[i])%mod;
	}
	fact[0]=1;
	for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
	ans=f*fact[n]%mod*qmi(fact[k]*fact[n-k]%mod,mod-2,mod)%mod;
	cout<<ans;
	return 0;
}