Submission #3001799

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int I=X;I<Y;I++)
#define REP(I,X,Y) for(int I=Y-1;I>=X;I--)
#define INF 1000000007
using namespace std;

vector<int> pow2{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912};
vector<long long> factorial(2,1);
long long nckmodp(int n,int k,int p){
  if(n < k || n <= 0 || k < 0)return 0;
  while(factorial.size() <= n){
    long long i = factorial.size();
    factorial.push_back(i*factorial[i-1]%p);
  }
  long long n1 = factorial[n],n2 = factorial[k],n3 = factorial[n-k];
  vector<long long> a2,a3;
  FOR(i,0,pow2.size()){
    a2.push_back(n2);
    a3.push_back(n3);
    n2 = (n2*n2)%p;
    n3 = (n3*n3)%p;
  }
  n2 = 1;
  n3 = 1;
  FOR(i,0,pow2.size()){
    if(pow2[i]&(p-2)){
      n2 *= a2[i];
      n3 *= a3[i];
      n2 %= p;
      n3 %= p;
    }
  }
  return (n1*n2%p)*n3%p;
}

int main(){
  int n,k;
  cin >> n >> k;
  cout << nckmodp(n-1+k,n-1,INF) << endl;
}

Submission Info

Judge Result