Kocke

시간 제한2초메모리 제한1024 MB

문제

도널드의 열세 번째 생일을 맞아 부모님이 새 레고 큐브 세트를 사 주셨다. 이 세트에는 크기가 같은 큐브가 $n$ 개 들어 있으며, $i$ 번째 큐브의 색은 $i$ 번이다. 도널드는 이 큐브로 벽을 쌓기로 했다.

도널드는 큐브를 놓을 수 있는 칸이 $k$ 개 있는 일렬의 레고 받침대 위에 벽을 쌓는다. 큐브는 다음 순서로 놓는다.

먼저 1번 색 큐브를 받침대의 아무 칸에 놓는다.
2번부터 $n$ 번까지의 큐브를 차례로, 직전에 놓은 큐브의 이웃 칸에 놓는다. 그 칸이 비어 있지 않으면 새 큐브는 그 칸에 이미 있는 큐브들 위에 올린다.

벽을 다 쌓은 뒤 도널드는 종이에 길이 $k$ 의 수열을 적는다. 수열의 $i$ 번째 원소는 $i$ 번째 칸 맨 위에 있는 큐브의 색이고, 그 칸에 큐브가 없으면 0이다.

도널드는 이렇게 적을 수 있는 서로 다른 수열이 몇 개인지 궁금해졌다. 두 수열은 어느 위치에서든 값이 하나라도 다르면 서로 다른 수열이다. 도널드는 답을 계산했지만 맞는지 확신하지 못해 도움을 청한다.

한 줄에 정수 $n$ 과 $k$ 가 주어진다 ( $2 \le n, k \le 5000$ ). $n$ 은 큐브의 개수, $k$ 는 받침대의 길이다.

답을 $10^9 + 7$ 로 나눈 나머지를 출력한다.

첫 번째 예시의 설명:

가능한 수열은 모두 다음과 같다. (0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1).

두 번째 예시의 설명:

가능한 수열 중 하나는 (0, 3, 2, 0, 0)이다. 도널드는 1번 큐브를 두 번째 칸에, 2번 큐브를 세 번째 칸에, 3번 큐브를 두 번째 칸에 놓아 이 수열을 만들 수 있다. 3번 큐브는 1번 큐브 위에 놓인다.