Little Monkey and the Bananas

Little Monkey loves to host his friends in the forest for dinner. His friends are numbered from $1$ to $N$, and each friend brings a gift called Big Banana when they arrive. The first friend always brings $1$ Big Banana. For every subsequent friend $i$ (with $i\ge2$), the number of bananas they bring is equal to the sum of all bananas given by the previous friends plus $i^K$ more.

This can be expressed by the recurrence:

$$ a_1=1, \quad a_i=\left(\sum_{j=1}^{i-1}a_j\right)+i^K, \quad \text{for } i\ge2. $$

Given $N$ and $K$, determine the number of bananas the $N$th friend gives modulo $10^9+7$.

inputFormat

The input consists of two integers, $N$ and $K$, separated by a space.

outputFormat

Output a single integer: the number of bananas given by the $N$th friend modulo $10^9+7$.

sample

1 2

1