11401 - 이항 계수 3

 

 

step 1

페르마 소정리에 의하면 $p$가 소수일 때 $a^{p-2} = a^{-1}$입니다. 즉, $x/y \pmod{p} = x*(y^{-1})\pmod{p} = x*(y^{p-2})\pmod{p}$ 입니다.

step 2

${n \choose k} = \frac{n*(n-1)*...*(n-k+1)}{1*2*...*m}$ 입니다. 분모와 분자를 각각 계산한 다음 모듈러를 취해주면 됩니다.

코드

#include<stdio.h>
long long int pow(long long int x, long long int y) {
	if (y == 1) return x;
	if (y == 0) return 1;
	long long int p = pow(x, y / 2);
	if (y % 2 == 1) return p * p % 1000000007 * x % 1000000007;
	else return p * p % 1000000007;
}
int main() {
	long long int n, m, i, cnt = 1, ch = 1;
	scanf("%lld %lld", &n, &m);
	for (i = 1; i <= m; i++) {
		cnt *= (n-i+1);
		cnt %= 1000000007;
	}
	for (i = 1; i <= m; i++) {
		ch *= i;
		ch %= 1000000007;
	}
	cnt *= pow(ch, 1000000005);
	cnt %= 1000000007;
	printf("%lld", cnt);
	return 0;
}