배열 초기화

여러 프로그래밍 언어에는 배열 전체나 일부를 특정 값으로 채우는 함수가 있다. Pascal에서는 fillchar(), Java에서는 Arrays.fill(), C++에서는 memset()이다. 새 프로그래밍 언어 J#에는 논리형 배열에만 쓸 수 있는 mark() 함수가 있다.

두 매개변수 $a$와 $b$로 호출한 mark 함수는 인덱스 $a$부터 $b$까지의 모든 배열 원소에 true를 대입한다. 예를 들어 1부터 번호가 매겨지고 처음에 모든 값이 false인 길이 4의 배열에 mark(1, 3)과 mark(2, 4)를 실행하면 배열 전체가 true로 채워진다.

J#를 배우기 시작한 사람들의 첫 과제 중 하나는 정확히 $M$번의 mark 연산을 포함하고, 처음에 false로 채워진 길이 $N$의 배열을 true로 완전히 채우는 프로그램을 작성하는 것이다.

이 과제를 빠르게 해결한 당신은 이제 생각한다. 이 일을 하는 서로 다른 방법은 몇 가지일까? 두 프로그램에서 1부터 $M$까지의 어떤 $i$에 대해 $i$번째 mark 연산이 서로 다른 매개변수로 실행되면 서로 다른 방법으로 본다. 이 수는 클 수 있으므로 $10^9+7$로 나눈 나머지를 구해야 한다.

첫째 줄에 두 자연수 $N$과 $M$이 주어진다. 이는 배열의 길이와 프로그램에 있어야 하는 mark 연산의 수이다. ($1 \le N, M \le 70$)

$N$개의 원소로 이루어진 배열을 $M$번의 mark 연산으로 true로 채우는 방법의 수를 $10^9+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)