题目描述

已知：

$\sum\limits_{i=1}^n i=1+2+ \dots +n= \frac{n*(n+1)}{2}$

$\sum\limits_{i=1}^n i^2=1^2+2^2+ \dots +n^2= \frac{n*(2n+1)*(n+1)}{6}$

$\sum\limits_{i=1}^n i^3=1^3+2^3+ \dots +n^3= (\frac{n*(n+1)}{2})^2$

求：$\sum\limits_{i=1}^n i^k=1^k+2^k+ \dots +n^k$ 模 $10^9+7$ 的值。

输入格式

一行两个整数 $n \ k \ ( 1 \le n \le 10^9 , 0 \le k \le 10^6 )$ 。

输出格式

输出一个整数，表示答案 $\bmod 10^{9}+7$ 的值。

输入输出样例 #1

输入 #1

4 1

输出 #1

10

输入输出样例 #2

输入 #2

4 2

输出 #2

30

输入输出样例 #3

输入 #3

4 3

输出 #3

100

输入输出样例 #4

输入 #4

4 0

输出 #4

4