Сложность: 40%
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек . Заяц может одним прыжком преодолеть не более ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы.
Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях и . Помогите директору написать программу, которая поможет вычислить это количество. Например, если и , то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.
Входные данные
В единственной строке записаны два натуральных числа и (). - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, – общее число ступенек лестницы.
Выходные данные
В единственную строку нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей. Так как ответ может получиться достаточно большим, выведите его по модулю .
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 33 | - | |
2 | 67 | 1 | Нет дополнительных ограничений |
STDIN | STDOUT |
1 3 | 1 |
2 7 | 21 |
3 10 | 274 |