Quân đoàn Caesar (Caesar's Legions)

Nguồn: Codeforces

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

Đề bài

Cần xếp một dãy gồm đúng $n_1$ lính chân và $n_2$ lính ngựa. Không được có quá $k_1$ lính chân liên tiếp và quá $k_2$ lính ngựa liên tiếp. Hãy đếm số đội hình.

Input

Dòng duy nhất chứa $n_1,n_2,k_1,k_2$.

Output

In số đội hình modulo $10^8$.

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

2 2 1 2

Output

3

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.