The Sum of the k-th Powers

题目描述：求 $(\sum_{i=1}^ni^k) \bmod (10^9+7)$。 数据范围：$1 \le n \le 10 ^ 9, 0 \le k \le 10 ^ 6$。

There are well-known formulas: , , . Also mathematicians found similar formulas for higher degrees. Find the value of the sum  modulo $ 10^{9}+7 $ (so you should find the remainder after dividing the answer by the value $ 10^{9}+7 $ ).

The only line contains two integers $ n,k $ ( $ 1<=n<=10^{9},0<=k<=10^{6} $ ).

Print the only integer $ a $ — the remainder after dividing the value of the sum by the value $ 10^{9}+7 $ .

4 1

10

4 2

30

4 3

100

4 0

4