Migrated from Lutece 631 敢说就敢做

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

beap总是自诩敢说又敢做，又到了情人节，为了体现自己的勇气可嘉，beap决定给自己喜欢的女生买玫瑰花，以此表达自己的爱意。到花店里，他发现一共有$K$种花，同时他从网上得知，送$N$朵花的花语是LOVE，所以他决定在所有的花里面选$N$朵出来送给心爱的女生，但是又为了显示自己买了那么多种花，他决定这$K$种花一定要都出现在这$N$朵里面。现在beap将这些花排成一排，他想知道满足条件的$N$朵花，能摆成多少种形态呢？

Input

多组测试数据

每组测试数据包含两个整数$N,K$($0 < N \leq 1000$, $0< K \leq 30$)，$N$代表花的朵数，$K$代表花的种类数。

Output

对于每个$N,K$，输出答案$mod\ 123456781$。

Samples

1 1
2 2

1
2

Resources

2012 UESTC ACM-ICPC Summer Training Team Selection 4