Bạn cộng thế nào? (How do you add?)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $N$ và $K$. Đếm số bộ có thứ tự gồm đúng $K$ số nguyên không âm có tổng bằng $N$. Hai bộ khác thứ tự được xem là khác nhau. In kết quả modulo $1{,}000{,}000$.

Input

Dòng duy nhất chứa $N,K$.

Output

In số cách modulo $1{,}000{,}000$.

Subtask

• Subtask 1 — 20 điểm: N <= 20; K <= 8. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: N <= 60; K <= 60. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= N <= 100; 1 <= K <= 100. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

20 2

Output

21

Giải thích

Với $N=20,K=2$, số hạng đầu có thể nhận mọi giá trị từ 0 đến 20; số hạng còn lại được xác định, nên có 21 cách.