거듭제곱의 합 1

1부터 $n$까지 모든 자연수의 $p$제곱을 더한 값을 $10^9+7$로 나눈 나머지를 구하시오. 즉, 다음 값을 구하시오.

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

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

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

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