Submission #1689851

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
template <int mod> struct ModInverse {
  ModInverse() {}
  ModInverse(int n) : n(n) {
    build();
  }

  int n;
  vector<long long> factorial, inverse;

  int operator()(int n, int k) {
    return Combination(n, k);
  }

  void build() {
    factorial.resize(n + 1);
    inverse.resize(n + 1);

    factorial[0] = 1;
    for (int i = 1; i <= n; ++i) {
      factorial[i] = i * factorial[i - 1] % mod;
    }

    inverse[n] = 1;
    for (int i = 1 << 30; i; i >>= 1) {
      inverse[n] = ((long long)inverse[n] * inverse[n]) % mod;
      if ((mod - 2) & i) {
        inverse[n] = ((long long)inverse[n] * factorial[n]) % mod;
      }
    }
    for (int i = n - 1; i > 0; --i) {
      inverse[i] = (inverse[i + 1] * (i + 1)) % mod;
    }
  }

  int Combination(int n, int k) {
    return factorial[n] * inverse[k] % mod * inverse[n - k] % mod;
  }
};

int main() {
  int h, w;
  cin >> w >> h;
  ModInverse<mod> Combination(h + w - 2);

  cout << Combination(h + w - 2, h - 1) << endl;
}

Submission Info

Judge Result