호기심 많은 수호자

N개 도시에 대해 모든 도시의 연결 도로 수가 K 이하인 레이블 트리의 개수를 센다.

보통7조합론동적 계획법트리아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

오아는 DC 우주에서 가장 오래된 행성 가운데 하나이고, 우주의 수호자들이 사는 곳이다. 수호자들은 우주에서 가장 강한 조직 가운데 하나인 그린 랜턴 군단을 관리한다. 그린 랜턴은 반지의 힘으로 하늘을 날지만, 오아의 주민이 모두 군단에 속하지는 않는다. 도로가 없어서 이런 주민은 도시 사이를 오가기 어렵다.

수호자들은 도로를 지어 오아의 도시를 연결하려 한다. 오아에는 도시가 NN개 있고, 어느 도시에서 다른 어느 도시로든 직접 또는 다른 도시를 거쳐 갈 수 있도록 양방향 도로 N1N-1개를 짓고 싶다. 특정 도시만 지나치게 유리해지는 것도 원하지 않아서, 한 도시에 연결되는 도로가 KK개를 넘지 않아야 한다는 조건을 걸었다.

예를 들어 도시가 3개이고 KK가 2이면 가운데에 놓을 도시를 고르는 방법에 따라 세 가지 계획이 나온다.

도시가 3개이고 K가 2일 때 가능한 세 가지 도로 계획

수호자들은 호기심이 많아서, 이 조건을 지키면서 도로 N1N-1개를 짓는 방법이 몇 가지인지 그린 랜턴에게 물었다. 군단의 일원인 당신이 NNKK를 받아 그 수를 세어라. 도시는 서로 구별되므로, 도로로 이어진 도시 쌍의 집합이 다르면 서로 다른 계획으로 센다.

입력

첫째 줄에 정수 NNKK가 공백으로 구분되어 주어진다. (1N1001 \le N \le 100, 1KN1 \le K \le N)

출력

조건을 만족하는 도로 계획의 수를 109+710^9+7로 나눈 나머지를 한 줄에 출력한다.