nCr

Given two integers n and r, find nCr. Since the answer may be very large, calculate the answer modulo 109+7

• Time : O(n log mod)
• Space : O(n)

c++

#define ll long long
class Solution{
    ll fact[1001];
    ll inv[1001];
    ll mod = 1e9 + 7;
    ll fac(ll n) {
        if(fact[n] != -1) return fact[n];
        return fact[n] = (n * fac(n-1)) % mod;
    }
    ll modpow(ll x, ll n) {
        if(n == 0) return 1;
        ll res = modpow(x, n>>1);
        res = (res * res) % mod;
        if(n & 1) res = (res * x) % mod;
        return res;
    }
    ll inve(ll n) {
        if(inv[n] != -1) return inv[n];
        return inv[n] = (modpow(n, mod - 2) * inve(n-1)) % mod;
    }
public:
    int nCr(int n, int r){
        if(n < r) return 0;
        memset(fact, -1, sizeof fact);
        memset(inv, -1, sizeof inv);
        inv[0] = fact[0] = inv[1] = fact[1] = 1;
        return (((fac(n) * inve(r)) % mod) * inve(n-r)) % mod;
    }
};