• 거듭제곱의 합을 계산하는 문제.
• 풀이 방법은 거듭제곱의 합을 참고. n≤50으로 매우 작기 때문에, O(n^2) DP를 이용해도 순식간에 풀린다
• 라그랑주 보간법을 이용한 코드는 거듭제곱의 합 1 참고.

"""Solution code for "BOJ 1492. 합".

- Problem link: https://www.acmicpc.net/problem/1492
- Solution link: http://www.teferi.net/ps/problems/boj/1492
"""

MOD = 1_000_000_007

from teflib import combinatorics


def main():
    N, K = [int(x) for x in input().split()]
    s = [N] + [None] * K
    comb_table = combinatorics.CombTable(K + 1, MOD)
    for i in range(1, K + 1):
        sigma = sum(comb_table.get(i + 1, p) * s[p] for p in range(i))
        s[i] = (pow(N + 1, i + 1, MOD) - 1 - sigma) * pow(i + 1, -1, MOD) % MOD
    print(s[K])


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.CombTable