The Sum of the k-th Powers

题意翻译

求 $\sum_{i=1}^ni^k \bmod (10^9+7)$

题目描述

There are well-known formulas: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF622F/5be9498766c9d969e3a6760cab8032bf2e4516ad.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF622F/136a02961e04e3ae077df756f5b50353eb1651d8.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF622F/ef5fbd3c33dc2a5f5200f977f6606feb4c647f7a.png). Also mathematicians found similar formulas for higher degrees. Find the value of the sum ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF622F/93e3cbcc0ffa2514081fc9f5724c4f98f477a6d1.png) 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 $ .

输入输出样例

输入样例 #1

4 1

输出样例 #1

10

输入样例 #2

4 2

输出样例 #2

30

输入样例 #3

4 3

输出样例 #3

100

输入样例 #4

4 0

输出样例 #4

4