跳至正文
题库1735
#1735

The Sum of the k-th Powers

查看题目操作

The Sum of the k-th Powers

题目描述

There are well-known formulas: , , . Also mathematicians found similar formulas for higher degrees.

Find the value of the sum modulo 109+7 (so you should find the remainder after dividing the answer by the value 109+7).

Input

The only line contains two integers n,k (1≤n≤109,0≤k≤106).

Output

Print the only integer a − the remainder after dividing the value of the sum by the value 109+7.

Examples

4 1
10
4 2
30
4 3
100
4 0
4