Caesar's Legions

# 题目描述 凯撒大帝喜欢让他的士兵列队。假设他的军队有$n_1$个步兵和$n_2$个骑兵。他认为超过$k_1$个步兵连续排列或是超过$k_2$个骑兵连续排列是不优雅的。请找出共有多少种优雅的列队方案数。 注：所有$n_1+n_2$个士兵都要被排列，且所有步兵和骑兵都视作相同。 # 输入输出格式 ## 输入格式： 一行包含四个空格隔开的正整数$n_1,n_2,k_1,k_2(1 \leq n_1, n_2 \leq 100, 1 \leq k_1, k_2 \leq 10)$，分别代表步兵的数量、骑兵的数量、最大的连续步兵数量和最大的连续骑兵数量。 ## 输出格式： 输出优雅的列队方案数，结果对$100000000(10^8)$取模 ## 说明 1表示步兵，2表示骑兵 第一个样例中，只有一种优雅的排列方式：121 第二个样例中，有五种优雅的排列方式：12122,12212,21212,21221,22121

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<=n_{1},n_{2}<=100,1<=k_{1},k_{2}<=10 $ ) which represent how many footmen and horsemen there are and the largest acceptable number of footmen and horsemen standing in succession, correspondingly.

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.

2 1 1 10

1

2 3 1 2

5

2 4 1 1

0

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