25974번 - 거듭제곱의 합 1

$1$부터 $n$까지 모든 자연수의 $p$ 거듭제곱의 합을 $10^9+7$로 나눈 나머지를 구하시오. 다시 말해,

$$\left(\sum_{k=1}^{n}k^p\right)\mod\left(10^9+7\right)$$

을 구하시오.

첫 줄에 $n$과 $p$가 공백을 사이에 두고 주어진다.

거듭제곱의 합을 $10^9+7$로 나눈 나머지를 출력한다.

• $1\leq n\leq 10^9$
• $0\leq p\leq 1000$