# The Sum of the k-th Powers

## 题目描述

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