Зайчик

Сложность: 40%

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек nn. Заяц может одним прыжком преодолеть не более kk ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы.

Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях kk и nn. Помогите директору написать программу, которая поможет вычислить это количество. Например, если k=3k=3 и n=4n=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

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

В единственной строке записаны два натуральных числа kk и nn (1kn1051 ≤ k ≤ n ≤ 10^5). kk - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, nn – общее число ступенек лестницы.

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

В единственную строку нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей. Так как ответ может получиться достаточно большим, выведите его по модулю 109+710^9 + 7.

Подзадачи

баллынеобх. подзадачиограничения
1

33

-

k,n1000k, n ⩽ 1000

2

67

1

Нет дополнительных ограничений

STDINSTDOUT
1 3
1
2 7
21
3 10
274