Задача G2. Собери свой учебный план

Данный шаг отличается от предыдущего формулировкой ограничений на входные данные. Перед проверкой решения задачи с формулировкой ограничений из этого шага, убедитесь, что это решение проходит и на предыдущем шаге.

Мальчик Слава очень любит учиться. В этом семестре ему предстоит изучить n предметов, по каждому из которых существует несколько вариантов программы любой сложности. В институте, в котором учится Слава, сложность программы по предмету измеряется в зачётных единицах — это любое натуральное число, причём чем оно больше, тем сложнее считается программа.

Добрый замдекана факультета, на котором учится Слава, не разрешает студентам переусложнять свой учебный план на семестр, поэтому он разрешает студентам выбирать программы по предметам, только если их суммарная сложность равна m зачётным единицам.

Как истинный комбинатор, Слава сразу увидел в сложившейся ситуации задачу — сколькими способами он может собрать свой учебный план на семестр, чтобы суммарная сложность программ по предметам была в точности равна m? Для каждого предмета в учебном плане Слава может выбирать любую сложность от 1 до m.

Поскольку ответ может быть слишком большой, Слава хочет знать остаток от деления его на 109+7.

Формат входных данных

В единственной строке входных данных записаны 2 натуральных числа n,m (1≤n,m≤105) — число предметов в семестре и суммарная сложность программ, которую необходимо набрать Славе в семестре соответственно (n≤m).

Формат выходных данных

В выходной файл выведите одно целое число — количество способов собрать учебный план по модулю 109+7.

Замечание

В первом тесте из условий Слава может набрать свой учебный план 3 способами:
1+3
2+2
3+1
Обращаем ваше внимание на то, что порядок, в котором идут слагаемые в учебном плане, важен.