Question

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

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

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

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

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

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

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

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

Замечание

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

Система оценки

Баллы за задачу будут начислены, если все тесты будут пройдены успешно.

Answer 1

Здравствуйте, вы являетесь участником олимпиады НТИ.  По правилам олимпиады нельзя использовать готовые решения для прохождения на последующие этапы. Т.к. вы нарушили правила, ваш аккаунт блокируется, и вы отстраняетесь от участия в НТИ. Желаем участия в следующем году.

С уважением,

Модераторы НТИ