Caesar's Legions

2000ms

262144K

Description:

Gaius Julius Caesar, a famous general, loved to line up his soldiers. Overall the army had n₁ footmen and n₂ horsemen. Caesar thought that an arrangement is not beautiful if somewhere in the line there are strictly more that k₁ footmen standing successively one after another, or there are strictly more than k₂ horsemen standing successively one after another. Find the number of beautiful arrangements of the soldiers.

Note that all n₁ + n₂ warriors should be present at each arrangement. All footmen are considered indistinguishable among themselves. Similarly, all horsemen are considered indistinguishable among themselves.

Input:

The only line contains four space-separated integers n₁, n₂, k₁, k₂ (1 ≤ n₁, n₂ ≤ 100, 1 ≤ k₁, k₂ ≤ 10) which represent how many footmen and horsemen there are and the largest acceptable number of footmen and horsemen standing in succession, correspondingly.

Output:

Print the number of beautiful arrangements of the army modulo 100000000 (10⁸). That is, print the number of such ways to line up the soldiers, that no more than k₁ footmen stand successively, and no more than k₂ horsemen stand successively.

Sample Input:

2 1 1 10

Sample Output:

Sample Input:

2 3 1 2

Sample Output:

Sample Input:

2 4 1 1

Sample Output:

Note:

Let's mark a footman as 1, and a horseman as 2.

In the first sample the only beautiful line-up is: 121

In the second sample 5 beautiful line-ups exist: 12122, 12212, 21212, 21221, 22121

Informação

Provedor Codeforces

Código CF118D