Bad Serial Inc. (BSI) produces integer sequences with length N, in which every element is an integer in range [1, M].
They call a sequence S is bad if all the M-substrings (substrings with length M) are bad.
They call an M-substring is bad if it’s not good. An M-substring is good if all the elements in the substring are the same or all the elements are distinct (different from each other).
The company BIS is designed to produce bad sequences. But how many different bad sequences are there? Since the answer will be very large, just output the result after module 987654321.
There are several cases. For each case, there is a line with two integers N, and M (1 ≤ N ≤ 100, 1 ≤ M ≤ 9).
The input ends up with two negative numbers, which should not be processed as a case.
Print the number of different bad sequences module 987654321 in a line for each case.