After a long ride out on the roads, Bertie's gang prefers to spend some time resting (and obviously drinking) in a pub, their motorcycles are properly lined up in front of the pub. At the end of the day each rider has his or her own bike and no one likes taking another one by mistake. They usually remember their bikes by their position. |
source: http://en.wikipedia.org/wiki/File:Motorcycles_parked_outside_the_Rajiv_Gandhi_Institute_ of_Technology.jpg |

The bikes are painted in a variety of colors, but there are still more bikes than colors. One day the bartender decides to be play a little practical joke and plans to tell Bertie that while the gang was happily getting drunk in the pub, he rushed out and reordered the bikes. The guys would surely notice if there was a bike of a different color parked in the spot where they left their own bike; so the only way to mix up the bikes is to shuffle them around in a way that the color of the bike in a given spot stays the same.

Unfortunately the bartender can't leave the bar unnoticed at the moment so he can't check the parking lot and count bikes. Instead, he is pondering how many different solutions exist for different number of bikes and colors.

Input is a list of *n*, *k* pairs (*n* being the number
of bikes and *k* being the number of possible colors). Last line of
the input is always "0 0". Your task is to calculate
how many different placements of the bikes he can pick from, for each input line.
However, since you do not know the exact coloring of the actual bikes, you need
to sum the number of solutions for each possible color setup. The bartender
dropped out of school after 6 grades, so he can count only up to 100000007.
To overcome this limitation, you need to submit your results modulo 100000007.

## Example input1 1 1 3 6 3 2 4 10 10 100 200 35 30 64 29 32 2 1000 2 1000 3 0 0 |
## Example output1 3 20160 20 21262936 93294537 48151294 39886421 15453915 84702802 36100834 |