URI Online Judge | 1937

Curious Guardians

By Stefano Tommasini Brazil

Timelimit: 1

Oa is one of the ancient worlds of the DC universe, it is there that inhabit the guardians of the universe. They administer the Green Lantern Corps, a major force in the universe! Everyone knows that the Green Lanterns can fly because of the power of the ring, but not all the inhabitants of Oa are part of the troop. For these people is difficult getting between cities, as there are no roads!

The guardians want to connect the cities of Oa building some roads. There are N cities in Oa, and they want to build N-1 road of both hands, so that you can get from one city to any other directly or indirectly. The guardians also do not want too much focus any city, so they established that no city can have more than K roads. For example, if we have three cities and K equals 2, we have three options:

The guardians though, are very curious, and asked the Green Lanterns if they were able to tell how many ways you can build N-1 road obeying these restrictions. Your task, as a member of the Green Lantern Corps is N and K data, satisfy the curiosity of guardians.


The input consists of a single line containing two integers N (1 ≤ N ≤ 102) and K (1 ≤ KN).


Your program should produce a single line containing a single integer, the problem response. As this response may be very large, print it module of 109 + 7.

Input Samples Output Samples

3 2


4 1


4 3