\(n\)과 작은 지수 \(k\)가 주어질 때 \(\sum_{i=1}^{n} i^k \bmod (10^9+7)\)을 구하시오. \(n\)이 최대 \(10^{18}\)까지 커질 수 있으므로 반복 대신 닫힌 형태나 차수 \((k{+}1)\)의 거듭제곱 합 다항식에 대한 라그랑주 보간을 사용한다.

한 줄에 두 정수 \(n\)과 \(k\)가 주어진다 (\(1 \le n \le 10^{18}\), \(0 \le k \le 5\)).

\(\sum_{i=1}^{n} i^k \bmod (10^9+7)\)을 출력한다.

riseoj 작성

출처 RiseOJ Basics