Buổi phỏng vấn hôn nhân (The Marriage Interview :-))

Nguồn: UVa

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

Đề bài

Xét hàm đệ quy trib(n, back) như đề gốc UVa 10446. Mỗi lần gọi hàm làm bộ đếm tăng 1; nếu $n\le0$ trả 0, nếu $n=1$ trả 1, còn lại gọi trib(n-i,back) với $1\le i\le back`. Hãy tính tổng số lần hàm được gọi.

Input

Dòng duy nhất chứa $n,back$. Với $n<0$, xem như $n=0$.

Output

In số lần gọi hàm.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

5 5

Output

41

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.