!!![백준] 11401번 이항 계수3

출처: [백준] 11401번 이항 계수3

---

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

---

출력

를 1,000,000,007로 나눈 나머지를 출력한다.

---

예제 입력 1

5 2

예제 출력 1

10

---

힌트

• 페르마의 소정리 이용

---

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: kjo7811

---

알고리즘 분류

• 수학
• 정수론
• 페르마의 소정리

---

시간 제한

---

풀이

---

소스코드 1

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
mod = 1000000007


def power(a, b):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:  # B가 짝수일 때
            return (power(a, b // 2) ** 2) % mod
        else:
            return (power(a, b // 2) ** 2 * a) % mod


# Factorial dp
fact = [1 for _ in range(N + 1)]

for i in range(2, N + 1):
    fact[i] = fact[i - 1] * i % mod

child = fact[N]
parent = (fact[K] * fact[N - K]) % mod

# 페르마의 소정리
print((child % mod) * (power(parent, mod - 2) % mod) % mod)

# -------------------------------------------------
# for i in range(2, N + 1):
#     fact[i] = fact[i - 1] * i
#
# child = fact[N]
# parent = fact[K] * fact[N - K]

# print(int(child / parent) % mod) ==> 메모리초과