← 返回题目列表

Codeforces · 118/D

D. 凯撒军团

中文机器翻译题面 查看原题

著名将军盖乌斯·朱利叶斯·凯撒喜欢排列他的士兵。总的来说,军队有n1个步兵和n2个骑兵。凯撒认为,如果队列中某处有严格多于 k1 名步兵依次连续站立,或者严格多于 k2 名骑兵依次连续站立,则这种安排并不美观。求士兵们布置的漂亮数量。

请注意,所有 n1 + n2 战士都应该出现在每次安排中。所有的步兵都被认为是没有区别的。同样,所有骑士之间都被认为是没有区别的。

输入

唯一一行包含四个空格分隔的整数 n1, n2, k1, k2 (1 ≤ n1, n2 ≤ 100, 1 ≤ k1, k2 ≤ 10),分别代表有多少步兵和骑兵以及可接受的连续站立的最大步兵和骑兵数量。

输出

打印军队美丽排列的数量模 100000000 (108)。也就是说,打印这样排列士兵的方式的数量,即不超过k1个步兵连续站立,不超过k2个骑兵连续站立。

示例

输入 #1

2 1 1 10

输出 #1

1

输入 #2

2 3 1 2

输出 #2

5

输入 #3

2 4 1 1

输出 #3

0

注意

让我们将步兵标记为 1,将骑兵标记为 2。

在第一个样本中,唯一漂亮的阵容是:121

在第二个样本中,存在 5 个漂亮的阵容:12122、12212、21212、21221、22121