CF118D Caesar's Legions

Gaius Julius Caesar, a famous general, loved to line up his soldiers. Overall the army had $ n_{1} $ footmen and $ n_{2} $ horsemen. Caesar thought that an arrangement is not beautiful if somewhere in the line there are strictly more that $ k_{1} $ footmen standing successively one after another, or there are strictly more than $ k_{2} $ horsemen standing successively one after another. Find the number of beautiful arrangements of the soldiers. Note that all $ n_{1}+n_{2} $ warriors should be present at each arrangement. All footmen are considered indistinguishable among themselves. Similarly, all horsemen are considered indistinguishable among themselves.

The only line contains four space-separated integers $ n_{1} $ , $ n_{2} $ , $ k_{1} $ , $ k_{2} $ ( $ 1

Print the number of beautiful arrangements of the army modulo $ 100000000 $ $ (10^{8}) $ . That is, print the number of such ways to line up the soldiers, that no more than $ k_{1} $ footmen stand successively, and no more than $ k_{2} $ horsemen stand successively.

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