CNK

struct CNK{
    const int mod = 1000000007;
    int mx;

private:
    vi fac , ifac;

public:
    CNK(int max){
        mx = max;

        fac.resize(max + 1);
        ifac.resize(max + 1);

        fac[0] = ifac[0] = 1;

        for(int i = 1 ; i <= max ; ++i){
            fac[i] = 1LL * fac[i - 1] * i % mod;
            ifac[i] = fpow(fac[i], mod - 2);
        }
    }

    int fpow(int a , int b){
        int ans = 1;
        while(b > 0){
            if(b & 1){
                ans = (1LL * ans * a) % mod;
            }
            a = (1LL * a * a) % mod;
            b /= 2;
        }
        return ans;
    }

    int cnk(int n , int k){
        assert(mx >= n);
        if (n < 0 || k < 0 || k > n) return 0;
        return 1LL * fac[n] * ifac[n - k] % mod * ifac[k] % mod;
    }
};