Submission #385802

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long ll;
#define REP(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = 1e9 + 7;

int N, K;
int fac[200000];
int inv[200000];

ll factorial(ll n) {
  if(n == 0) return 1;
  if(fac[n]) return fac[n];
  return fac[n] = n * factorial(n-1) % MOD;
}

ll binaryPower(ll a, ll r) {
  if(r == 0) return 1;
  if(r % 2 == 0) return binaryPower(a*a % MOD, r / 2);
  return a * binaryPower(a, r - 1) % MOD;
}

ll inverseFactorial(ll n) {
  if(inv[n]) return inv[n];
  if(n == N+K-1) return inv[n] = binaryPower(factorial(n), MOD - 2);
  return inv[n] = inverseFactorial(n+1) * (n+1) % MOD;
}

int main() {
  cin >> N >> K;
  ll ans = 0;
  ans = factorial(N+K-1) * inverseFactorial(N-1) % MOD;
  ans = ans * inverseFactorial(K) % MOD;
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result