(coreward.*)

Kỳ thi Tin học trẻ tỉnh thường có các nhà tài trợ và các mạnh thường quân tặng phần thưởng cho các em đạt giải cao. Lần tổ chức này, để tổ chức lễ tuyên dương các em có thành tích tốt, ban tổ chức đã nhận được sự quan tâm của nhiều nhà tài trợ cũng như các mạnh thường quân là những doanh nhân giàu có. Trong đó, có một nhà tài trợ đã có ý định đưa đến buổi lễ \(m\) gói quà (các gói quà này có trị giá tương đương nhau) để phát cho \(n\) em đạt thành tích tốt nhất. Nhà tài trợ này muốn tạo sự bất ngờ cho tất cả nên đã đưa ra cách phát thưởng dựa trên danh sách \(n\) em có thành tích học tập tốt nhất, các em sẽ lên xếp hàng thành một đường thẳng, em có thứ hạng cao hơn sẽ được đứng trước em có thứ hạng thấp hơn. Đại diện của nhà tài trợ sẽ đứng ra phát các gói quà cho \(n\) học sinh đó theo quy tắc: Em đứng trước sẽ được nhận số gói quà (một em có thể nhận nhiều gói quà) không ít hơn số gói quà của em đứng ở phía sau nhận. Cũng vì một số lý do nào đó mà một số em cũng không nhận được gói quà nào (có thể là dành cho nhà tài trợ khác tặng quà).

Gọi \(t1,\ t2,\ ...,\ tn\) lần lượt là tổng số gói quà em thứ \(1,\ 2,\ ...,\ n\) nhận được (tương ứng với thứ hạng từ cao xuống thấp) thì \(t1 > t2\ > \ ...\ > \ tn - 1\ > \ tn\ > \ 0\) và \(t1\ + \ t2\ + \ ...\ + \ tn - 1\ + \ tn\ = \ m\)

Yêu cầu: Hãy cho biết có bao nhiêu cách phát quà khác nhau mà nhà tài trợ có thể phát.

Dữ liệu vào:

+ Ghi 2 số nguyên dương \(m\) và \(n\ (m,\ n\ < 1000)\).

Kết quả:

+ Ghi một số nguyên duy nhất là số cách phát thưởng tính được chia lấy phần dư cho 123456789.

Ví dụ:

Giải thích: Phát 3 gói quà cho 2 em

Cách 1: em thứ 1 nhận được 3 gói quà, em thứ 2 nhân đươc 0 gói quà;

Cách 2: em thứ 1 nhận được 2 gói quà, em thứ 2 nhận được 1 gói quà;

Có 2 cách phát quà.