On Saint Valentine's Day, Alex imagined to present a special pendant to his girl friend made by K kind of pearls. The pendant is actually a string of pearls, and its length is defined as the number of pearls in it. As is known to all, Alex is very rich, and he has N pearls of each kind. Pendant can be told apart according to permutation of its pearls. Now he wants to know how many kind of pendant can he made, with length between 1 and N. Of course, to show his wealth, every kind of pendant must be made of K pearls.
Output the answer taken modulo 1234567891.