(Elice / 수학 / Python) K번 곱하기

K번 곱하기

자연수 N과 K가 있습니다. 심심한 체셔는 1부터 N까지의 수를 K 번씩 곱한 후 더하려고 합니다.

식으로 나타내면 다음과 같습니다.

1K+2K+...++NK1^K + 2^K + ... + + N^K1K+2K+...++NK

계산 결과를 1,000,000,009로 나눈 수를 출력하는 프로그램을 작성하세요.

 

입력

• 자연수 N과 K를 입력합니다.

             (1<=N<=1,000,000,000)

                       (1<=K<=50)

출력

• 1K+2K+...++NK1^K + 2^K + ... + + N^K1K+2K+...++NK를 1,000,000,009로 나눈 나머지를 출력합니다.

입력 예시

4 2

출력 예시

30

소스 코드

import math
PRIME = 1000000009

def combination(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)
    
def mod_power(a, b):
    if b == 0:
        return 1
    if b == 1:
        return a % PRIME
        
    x = mod_power(a, b//2)
    
    if b % 2 == 1:
        return a*((x*x) % PRIME) % PRIME
    return (x*x) % PRIME
    
def main():
    inp = list(map(int, input().split()))
    N = inp[0]
    K = inp[1]
    k_sums = [0] * (K+1)
    k_sums[0] = N
    
    for k in range(1, K+1):
        k_sums[k] = mod_power(N+1, k+1) - 1
        #print(k_sums[k])
        for p in range(0, k):
            k_sums[k] -= combination(k+1, p) * k_sums[p] % PRIME
        k_sums[k] *= mod_power(k+1, PRIME-2)
        k_sums[k] %= PRIME
        
    print(int(k_sums[K]) % PRIME)
    
if __name__ == "__main__":
    main()