시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Во многих языках программирования есть функции, которые отвечают за заполнение всего массива или некоторой его части определенным значением. В языке 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$.
В первой строке входного файла даны два натуральных числа $N$ и $M$ --- длина массива и количество операций mark
, которые должны быть в программе. ($1 \le N, M \le 70$).
В единственной строке выходного файла выведите остаток от деления числа способов заполнить массив из $N$ элементов значениями true
с помощью $M$ вызовов операции mark
на число $10^9+7$.
2 2
7
Искомые варианты:
mark(1, 1); mark(1, 2)
mark(1, 1); mark(2, 2)
mark(1, 2); mark(1, 1)
mark(1, 2); mark(1, 2)
mark(1, 2); mark(2, 2)
mark(2, 2); mark(1, 1)
mark(2, 2); mark(1, 2)