The Sum of the k-th Powers

Description:

Input:

The only line contains two integers n, k (1 ≤ n ≤ 10⁹, 0 ≤ k ≤ 10⁶).

Output:

Print the only integer a — the remainder after dividing the value of the sum by the value 10⁹ + 7.

Sample Input:

4 1

Sample Output:

10

Sample Input:

4 2

Sample Output:

30

Sample Input:

4 3

Sample Output:

100

Sample Input:

4 0

Sample Output:

4