Caesar's Legions

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. 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$.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

2 2 1 2

Output

3

Explanation

The output follows directly from the rules above.