Teningasafn

Atli owns an awful lot of dice, so many that it’s becoming hard to keep track of it all. Thus you have been assigned the task of measuring his dice. Being a bit of a collector, all his dice are different size and Atli owns one die of each integer side length from size one to $n$. His dice are $k$-dimensional, so if the side length is $x$ then its volume is $x^ k$. The volumes are thus $1^ k, 2^ k, \dots $ up to $n^ k$.

Given $n$ and $k$ can you find the total volume of the dice? This volume might be very large, so the answer should be returned modulo $10^9 + 7$.

Input

The input is one line with two integers $n$ ($1 \leq n \leq 10^{18}$) and $k$ ($1 \leq k \leq 10^3$).

Output

Print the total volume modulo $10^9 + 7$.

Scoring

3 3

36

100 1

5050

276919944311283466 692

764638923