Monkey's Bananas

A hospitable monkey invites his forest friends to a feast. The friends are numbered from \(1\) to \(n\). Each friend brings him some gifts: delicious bananas. The first friend brings exactly \(1\) banana. After that, when the \(i\)-th friend (for \(i \ge 2\)) arrives, he brings a number of bananas equal to the sum of all bananas brought by the previous friends plus \(i^k\) bananas. That is, define \(f(1) = 1\) and for \(i \ge 2\):

[ f(i) = \left( \sum_{j=1}^{i-1} f(j) \right) + i^k, \quad i \ge 2, ]

For example, when \(k = 2\), the first few values of \(f(i)\) are:

[1,; 5,; 15,; 37,; 83, \ldots]

And when \(k = 3\), they are:

[1,; 9,; 37,; 111, \ldots]

Your task is to compute the number of bananas given by the \(n\)-th friend modulo \(10^9+7\). In other words, given \(n\) and \(k\), output \(f(n) \bmod (10^9+7)\).

inputFormat

The input consists of two integers \(n\) and \(k\) separated by space or newline.

\(n\): the number of the friend whose gift count you need to compute.
\(k\): the exponent used in the recurrence relation.

outputFormat

Output a single integer representing the number of bananas given by the \(n\)-th friend modulo \(10^9+7\).

sample

1 2

1