이항계수의 빠른 계산
서론 $\binom{N}{K}$ 는 $N$개의 구분이 되는 물체 중 $K$개를 고르는 가짓수이고, 이를 이항계수라고 부른다. 이항계수는 한 조합론적 상황에서 많이 사용된다. 이 $\binom{N}{K} = \dfrac{N!}{K!(N-K)!}$임이 잘 알려져 있다. 이 수를 소수가 아닌 임의의 수 $M$으로 나눈 나머지를 구하는 방법에 대해서 알아본다. Naive 이항계수를 $M$으로 나눈 나머지를 구하는 가장 쉬운 방법은 실제로 $N!$을 그냥 1부터 $N$까지의 모든 수를 곱하는 것으로 계산하는 것이다. 하지만 이럴 경우에 나눗셈이 잘 되지 않는다. 예를 들어서, $M=9$인 경우에는, $6! = 720$과 $7!=5040$을...