D. Легионы Цезаря
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Знаменитый полководец Гай Юлий Цезарь любил выстраивать воинов своей армии в шеренгу. Всего в армии было n1 пехотинцев и n2 всадников. Цезарь считал, что расстановка не красивая, если где-то в строю стоит подряд строго больше k1 пехотинцев или строго больше k2 всадников. Найдите количество красивых расстановок воинов.

Учтите, что в каждой расстановке должны присутствовать все n1 + n2 воинов. Все пехотинцы считаются неразличимыми между собой. Аналогично, все всадники считаются неразличимыми между собой.

Входные данные

В единственной строке через пробел записаны четыре целых числа n1, n2, k1, k2 (1 ≤ n1, n2 ≤ 100, 1 ≤ k1, k2 ≤ 10) — количество пехотинцев и всадников в армии, а также наибольшее допустимое количество стоящих подряд пехотинцев и всадников, соответственно.

Выходные данные

Выведите количество красивых расстановок войск по модулю 100000000 (108), то есть количество таких расстановок, где подряд стоит не более k1 пехотинцев и не более k2 всадников.

Примеры
Входные данные
2 1 1 10
Выходные данные
1
Входные данные
2 3 1 2
Выходные данные
5
Входные данные
2 4 1 1
Выходные данные
0
Примечание

Обозначим пехотинца как 1, а всадника как 2.

В первом примере единственное красивое построение: 121

Во втором примере существует 5 красивых построений: 12122, 12212, 21212, 21221, 22121