Function

In this problem, a function means a function that sends every integer from 1 to $n$ to an integer from 1 to $n$. For example, when $n = 3$, one possible function $g$ is $g(1) = 1$, $g(2) = 3$, $g(3) = 1$.

Define $f^j(x)$ as follows.

• $f^0(x) = x$ for every valid $x$.
• $f^{j+1}(x) = f^j(f(x))$ for every valid $x$ and $j$.

The following notation is defined.

• $G(f, w)$ is the set of the values $f^r(x)$ taken over every $x$ with $1 \le x \le n$ and every $r$ with $r \ge w$.
• $S(f, w)$ is the size of $G(f, w)$.
• $Z(f)$ is the minimum of $S(f, w)$ over all nonnegative integers $w$.
• $A(y)$ is the set of the functions $f$ with $Z(f) = y$.

Given $n$ and $k$, write a program that computes the size of $A(k)$ modulo 1,000,000,007.

The first line contains $n$ and $k$, separated by a space. ($1 \le n \le 5000$, $0 \le k \le n$)

Print the size of $A(k)$ modulo 1,000,000,007 on the first line.

For $n = 2$ there are 4 functions in total. Call them $a$, $b$, $c$, $d$.

• $a(1) = 1$, $a(2) = 1$
• $b(1) = 1$, $b(2) = 2$
• $c(1) = 2$, $c(2) = 1$
• $d(1) = 2$, $d(2) = 2$

$a$ and $d$ belong to $A(1)$, and $b$ and $c$ belong to $A(2)$.