Макс захотел приобрести себе шкафчик, в котором можно было бы хранить различные вещи. У шкафчика должно быть $$$N$$$ ящиков, расположенных вертикально друг над другом.
В мебельмом магазине Максу показали множество различных шкафчиков, а также особо отметили, что некоторые ящики в них могут закрываться на замок.
Однако Макс быстро сообразил, что даже если ящик закрывается на замок, это не всегда гарантирует, что до его содержимого нельзя будет добраться без ключа: если ящик непосредственно над рассматриваемым не запирается, то его можно просто вынуть из шкафчика, и тогда откроется доступ к запертому ящику.
Поэтому Макс считает ящик шкафчика надёжным, если выполняются два условия:
- Во-первых, этот ящик должен закрываться на замок;
- Во-вторых, либо этот ящик должен быть самым верхним, либо ящик сразу над ним тоже должен закрываться на замок.
Максу нужно, чтобы из $$$N$$$ ящиков шкафчика ровно $$$M$$$ были надёжными. Как оказалось, получить такой шкафчик можно различными способами. Например, ниже показано, как можно сделать шкафчик из $$$5$$$ ящиков, $$$3$$$ из которых надёжны (серым закрашены запирающиеся ящики, зелёным — запирающиеся и надёжные).
Помогите Максу определить, сколько существует способов собрать интересующий его шкафчик.
Выходные данные
Выведите одно целое число — количество видов шкафчиков из $$$N$$$ ящиков, у которых ровно $$$M$$$ ящиков надёжны. Так как ответ может оказаться очень большим, выведите остаток от его деления на $$$1000000007$$$.