comb_mod.cpp

const int MOD = 1000000007;

int exp_mod(long long a, long long b, int m) {
	long long res = 1;
	while (b > 0) {
		if (b&1)
			res = (res * a)%m;
		a = (a * a)%m;
		b >>= 1;
	}
	return (int)res;
}

int fact_mod(int n, int m) {
	long long res = 1;
	for (int i=n; i>0; --i)
		res = (res * i)%m;
	return (int)res;
}

int comb_mod(int n, int r) {
	long long res = 1;
	for (int i=0; i<r; ++i)
		res = (res * (n - i) )%MOD;
	return ( res * exp_mod(fact_mod(r, MOD), MOD-2, MOD) ) % MOD;
}