Functions to calculate Binomial Coefficients modulo 1000000007

binomial_coefficients.cpp

#define MAX 1000000007
#define FACT_MAX 250

int add(int a, int b){
	return (a + b) % MAX;
}

int mul(int a, in b){
	return ((long long)a * b) % MAX;
}

int powMod(int a, int b){
	int res = 1;
	for (; b; b >>= 1){
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
	}
	return res;
}

int modInverse(int a){
	return powMod(a, MAX - 2);
}

int fact[FACT_MAX], invfact[FACT_MAX];

// To generate factorials of numbers up to FACT_MAX.
// This function should be called once in main() 
void genFact(){
	fact[0] = invfact[0] = 1;
	for (int i = 1; i < FACT_MAX; i++){
		fact[i] = mul(fact[i-1], i);
		invfact[i] = modInverse(fact[i]);
	}
}

int C(int n, int k){
	return n < k ? 0 : mul(fact[n], mul(invfact[k], invfact[n-k]));
}