问题描述

N 个 相同 的球放到 M 个 相同 的盒子里，不允许 有空盒子，任意两个盒子里放的球的个数不能相同。有多少种不同的放法？

答案可能很大，你需要将其 mod 123456789 后输出。

问题输入

一行，两个整数 N 和 M，以空格分开

输出

不同的放法种数 mod 123456789 的值

样例输入

7 3

样例输出

1

数据范围

50%的数据：1 ≤ n, k ≤ 20

100%的数据：1 ≤ n, k ≤ 1000