초입방체 모음

Atli는 엄청나게 많은 초입방체를 가지고 있으며, 그 수가 너무 많아 관리하기 어려워졌다. 따라서 여러분은 그의 초입방체들을 측정하는 일을 맡게 되었다. 수집가 기질이 있는 Atli의 초입방체들은 모두 크기가 서로 다르며, Atli는 하나부터 $n$까지 각 정수 크기의 초입방체를 하나씩 가지고 있다. 그의 초입방체들은 $k$차원이므로, 한 초입방체의 한 변의 길이가 $x$이면 그 부피는 $x^k$이다. 따라서 초입방체들의 부피는 $1^k, 2^k, \dots$부터 $n^k$까지이다.

$n$과 $k$이 주어졌을 때, 초입방체들의 전체 부피를 구할 수 있는가? 이 부피는 매우 클 수 있으므로, 답을 $10^9 + 7$로 나눈 나머지를 구해야 한다.

점수

그룹 | 점수 | 제한

1 | 30 | $1 \leq n \leq 10^6$

2 | 30 | $1 \leq k \leq 3$

3 | 40 | 추가 제한 없음

입력은 두 정수 $n$ ($1 \leq n \leq 10^{18}$)와 $k$ ($1 \leq k \leq 10^3$)가 있는 한 줄로 주어진다.

전체 부피를 $10^9 + 7$로 나눈 나머지를 출력한다.