B. The Great Mixup (1000 points)

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.


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 input

1 1
1 3
6 3
2 4
10 10
100 200
35 30
64 29
32 2
1000 2
1000 3
0 0

Example output