시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.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$.

예제 입력 1

2 2

예제 출력 1

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)