11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net PS의 난이도가 올라가다 보면 같은 문제를 좀 더 효율적인 시간, 공간 복잡도로 구현해야 하는 순간이 온다. 이항 계수를 구할 때 n의 값이 너무 크면 메모이제이션(dp)으로도 해결하지 못한다. 문제가 요구하는 정답이 이항 계수의 모듈러 연산 값이라면, 페르마의 소정리와 곱셈의 역원을 활용하여 답을 찾을 수 있겠다. 페르마의 소정리 p가 소수라면, $$ a^{p - 1} \equiv 1\pmod{p} $$ 해당 식의 좌변과 우변이 동치이므로, $$\therefore a \times a^..