Знаменитый полководец Гай Юлий Цезарь любил выстраивать воинов своей армии в шеренгу. Всего в армии было n1 пехотинцев и n2 всадников. Цезарь считал, что расстановка не красивая, если где-то в строю стоит подряд строго больше k1 пехотинцев или строго больше k2 всадников. Найдите количество красивых расстановок воинов.
Учтите, что в каждой расстановке должны присутствовать все n1 + n2 воинов. Все пехотинцы считаются неразличимыми между собой. Аналогично, все всадники считаются неразличимыми между собой.
Выходные данные
Выведите количество красивых расстановок войск по модулю 100000000 (108), то есть количество таких расстановок, где подряд стоит не более k1 пехотинцев и не более k2 всадников.
Примечание
Обозначим пехотинца как 1, а всадника как 2.
В первом примере единственное красивое построение: 121
Во втором примере существует 5 красивых построений: 12122, 12212, 21212, 21221, 22121
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 1 10
|
1
|
|
2
|
2 3 1 2
|
5
|
|
3
|
2 4 1 1
|
0
|