2499 - The Sum of the k-th Powers

2499.The Sum of the k-th Powers

Time Limit: 1s Memory Limit: 256MB

There are well-known formulas: $2499_1.png$ , $2499_2.png$ , $2499_3.png$ . Also mathematicians found similar formulas for higher degrees.Find the value of the sum $2499_4.png$ modulo 109+7 (so you should find the remainder after dividing the answer by the value 109+7).

Input Format(From the terminal/stdin)

Input The only line contains two integers n,k (1 \le n \le 109,0 \le k \le 106).

Output Format(To the terminal/stdout)

Output Print the only integer a - the remainder after dividing the value of the sum by the value 109+7.

Sample Input 1

Copy

4 1
 · \n

Sample Output 1

Copy

10
  \n

Sample Input 2

Copy

4 2
 · \n

Sample Output 2

Copy

30
  \n

Sample Input 3

Copy

4 3
 · \n

Sample Output 3

Copy

100
   \n

Sample Input 4

Copy

4 0
 · \n

Sample Output 4

Copy

4
 \n

Submit

请先登录

Submit

题解(0)