Submission #38038241

---

Source Code Expand

#include<bits/stdc++.h>
#define mod 1000000007

using namespace std;

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

long long factorial[524288];
long long invfact[524288];

void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<524288;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[524287]=modular_inverse(factorial[524287]);
  for(i=524286;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}

long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

#define DEG 10005

int main(){
  cfact();
  long long n,k;
  cin >> n >> k;
  vector<long long> e(k);
  for(auto &nx : e){cin >> nx;}

  vector<long long> poly(DEG);
  poly[0]=1;
  for(int tim=0;tim<n;tim++){
    for(int i=1;i<DEG;i++){
      poly[i]+=poly[i-1];
      poly[i]%=mod;
    }
  }
  long long res=0;
  for(long long i=0;i<=n;i++){
    long long del=calcnCr(n,i);
    if(i%2){del=(mod-del)%mod;}
    for(auto &nx : e){
      del*=poly[nx];
      del%=mod;
    }
    res+=del;res%=mod;

    for(int j=DEG-1;j>=1;j--){
      poly[j]+=(mod-poly[j-1]);
      poly[j]%=mod;
    }
    for(int j=2;j<DEG;j++){
      poly[j]+=poly[j-2];
      poly[j]%=mod;
    }
  }
  cout << res << "\n";
  return 0;
}

Submission Info

Judge Result