Curious Guardians

Count labeled trees on N cities where every vertex has degree at most K.

Medium7CombinatoricsDynamic programmingTreeNo attempts yetTime limit1sMemory limit512 MB

Problem

Oa is one of the oldest planets in the DC universe, and the guardians of the universe live there. The guardians run the Green Lantern Corps, one of the strongest forces in the universe. A Green Lantern flies by the power of the ring, but not every inhabitant of Oa belongs to the Corps. Those inhabitants have a hard time moving between cities, because there are no roads.

The guardians want to connect the cities of Oa by building roads. Oa has NN cities, and the guardians want to build N1N-1 two-way roads so that you can get from any city to any other one, directly or through other cities. They also do not want any single city to gain too much, so they require that no city has more than KK roads attached to it.

For example, with three cities and KK equal to 2 there are three plans, one for each choice of the city placed in the middle.

The three possible road plans for three cities with K equal to 2

The guardians are curious, so they asked the Green Lanterns how many ways there are to build the N1N-1 roads under these rules. As a member of the Corps, take NN and KK and count them. The cities are distinguishable, so two plans are different when the set of city pairs joined by a road differs.

Input

The first line contains two integers NN and KK separated by a space. (1N1001 \le N \le 100, 1KN1 \le K \le N)

Output

Print on one line the number of road plans that satisfy the rules, modulo 109+710^9+7.