# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
58431572 |
Practice:
Zory |
891E
- 26
|
C++14 (GCC 6-32)
|
Accepted
|
186 ms
|
7840 KB
|
2019-08-07 15:05:44 |
2019-08-07 15:05:44 |
|
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
#define double long double
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define mid (l+r)/2
#define lc 2*x
#define rc 2*x+1
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
void add(int &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,ll e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int N=1e6+10;
ll A[N];
void main()
{
int n=qread(),K=qread();
A[0]=1;ll pp=1;
for(int i=1;i<=n;i++)
{
int a=qread();pp=pp*a%MOD;
for(int j=n;j>=1;j--) A[j]=(A[j]*a-A[j-1])%MOD;A[0]=A[0]*a%MOD;
}
ll ans=0;
for(int i=0,down=1;i<=n and i<=K;i++)
{
(ans+=A[i]*invm(qpower(n,i))%MOD*down%MOD )%=MOD;
down=(ll)down*(K-(i+1)+1)%MOD;
}
write((pp-ans+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}
Click to see test details