序列求和

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

已知T(n) = n^k,S(n) = T(1)+T(2)+T(3)+.......+T(n),求S(n)。
 

Input

多组输入,每组两个整数n,k(1<=n<=10^18,1<=k<=2000)

Output

由于结果很大,输出和S(n)%1000000007

Sample Input

4 1
4 2

Sample Output

10 
30

Hint


Source