함수

이 문제에서 함수는 1부터 $n$까지의 정수를 1부터 $n$까지의 정수로 보내는 함수를 뜻한다. 예를 들어 $n = 3$일 때 $g(1) = 1$, $g(2) = 3$, $g(3) = 1$은 가능한 함수 $g$의 한 예이다.

$f^j(x)$는 다음과 같이 정의한다.

• 모든 올바른 $x$에 대해 $f^0(x) = x$
• 모든 올바른 $x$와 $j$에 대해 $f^{j+1}(x) = f^j(f(x))$

새로운 표현은 다음과 같이 정의한다.

• $G(f, w)$는 $1 \le x \le n$인 $x$와 $w$ 이상인 $r$에 대한 $f^r(x)$ 값의 집합이다.
• $S(f, w)$는 $G(f, w)$의 크기이다.
• $Z(f)$는 모든 음이 아닌 정수 $w$에 대한 $S(f, w)$의 최솟값이다.
• $A(y)$는 $Z(f) = y$인 함수 $f$의 집합이다.

$n$과 $k$가 주어졌을 때, $A(k)$의 크기를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 $n$과 $k$가 공백으로 구분되어 주어진다. ($1 \le n \le 5000$, $0 \le k \le n$)

첫째 줄에 $A(k)$의 크기를 1,000,000,007로 나눈 나머지를 출력한다.

$n = 2$이면 함수를 모두 4개 만들 수 있다. 이를 각각 $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$와 $d$는 $A(1)$에 속하고, $b$와 $c$는 $A(2)$에 속한다.