백준 15791번: 세진이의 미팅

문제

문제 바로가기> 백준 15791번: 세진이의 미팅

풀이

페르마의 소정리를 이용하여 문제를 풀어야 시간초과가 발생하지 않는다. mypow함수를 log 시간 안에 해결하도록 만들어 줘야한다.

mod = 1000000007
def mypow(a, b):
    result = 1
    while(b>0):
        if(b&1) :
            result*=a
            result%=mod
        b = b>>1
        a*=a
        a%=mod
    return result

def solution():
    import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a, b = 1, 1
    for i in range(2, n+1):
        a*=i
        a%=mod
    for i in range(2, m+1):
        b*=i
        b%=mod
    for i in range(2, n-m+1):
        b*=i
        b%=mod
    print(a*mypow(b, mod-2)%mod)
solution()