문제 출처 : https://www.acmicpc.net/problem/11401

---

문제 파악

우리가 구해야 하는 값은 이항계수(N,K)이다.

이항계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수 인데

공식으로는

N! / ((N-K)! x K!) 이다.

문제는 N의 범위가 최대 4,000,000이라는 점.

• 팩토리얼 값은 너무 커진다.
• 모듈러 연산은 1,000,000,007 (10^9+7) 이며 소수다.
• 우리는 결국 다음을 구해야 한다:

모듈러 연산이란 파이썬 기호로는 '%' 이며
a % b 하면 a를 b로 나눴을 때 나머지를 리턴하는 연산이다.

---

핵심 아이디어

1) 나눗셈을 모듈러에서 계산하는 법

A / B mod p
→ 이렇게는 계산이 불가능함.

대신

A * (B^{-1}) mod p

즉, B의 역원이 필요하다.

---

2) 역원을 구하는 방법 — 페르마의 소정리

p = 1,000,000,007 은 소수이므로,

B^{-1} = B^(p-2) mod p

이걸 그대로 쓰면 된다.

결국 최종 공식은 아래처럼 된다.

(N C K) mod p
= N! (K!)^(p-2) ((N-K)!)^(p-2) mod p

이게 그대로 우리가 구현할 식이다.

---

전체 구조

1. fact 배열로 N! 까지 미리 계산
2. 분할정복 거듭제곱(BOJ 1629과 동일한 power 함수)으로 역원 계산
3. 공식 그대로 계산

---

해답 및 풀이

import sys
input = sys.stdin.readline

MOD = 1_000_000_007

# 분할 정복으로 거듭제곱 (1629번의 power 함수와 동일한 원리)
def mod_pow(a, b):
    if b == 1:
        return a % MOD

    half = mod_pow(a, b // 2)

    if b % 2 == 0:
        return (half * half) % MOD
    else:
        return (half * half * a) % MOD


# 입력
N, K = map(int, input().split())

# 팩토리얼 테이블 미리 만들기
fact = [1] * (N + 1)
for i in range(2, N + 1):
    fact[i] = (fact[i - 1] * i) % MOD

# N! * (K! * (N-K)!)^{-1} % MOD
denom = (fact[K] * fact[N - K]) % MOD

# denom^{-1} = denom^{MOD-2} % MOD
inv = mod_pow(denom, MOD - 2)

print((fact[N] * inv) % MOD)