чемпионаты Спб: Чемпионат СПБ 2012

Во многих языках программирования есть функции, которые отвечают за заполнение всего массива или некоторой его части определенным значением. В языке Pascal это функция fillchar(), в Java — Arrays.fill(), в C++ — memset(). В новом языке программирования J# появилась функция mark(), которая умеет работать только с массивами логического типа.

Функция mark, вызванная от двух параметров \(a\) и \(b\), присваивает всем элементам массива с индексами от \(a\) до \(b\) включительно значение true, Так, если взять массив длины \(4\), элементы которого нумеруются с единицы и все значения в котором изначально равны false, и выполнить с ним операции mark(1, 3) и mark(2, 4), то весь массив окажется заполнен значениями true.

Одним из первых заданий для тех, кто начинает изучать J#, является написание программы, содержащей ровно \(M\) операций mark, и полностью заполняющей значениями true массив длины \(N\), изначально заполненный значениями false.

Вы быстро справились с этим заданием, и теперь задумались: сколькими различными способами это можно сделать? Различными считаются такие способы, в которых \(i\)-я операция mark в двух программах запущена с разными параметрами хотя бы для одного \(i\) от \(1\) до \(M\). Это число может быть большим, поэтому требуется посчитать его по модулю \(10^9 + 7\).