농산물 직거래 장터를 방문한 Busy Beaver는 거리의 마술사를 구경하기 위해 멈춰 섰습니다. 마술사는 $N$개의 상자를 일렬로 늘어놓고, 각 상자에는 $M$비트 음이 아닌 정수 $a_1, a_2, \dots, a_N$이 들어 있습니다. 여기서 모든 $1 \le i \le N$에 대해 $0 \le a_i < 2^M$입니다.

마술사는 일련의 마법 교환을 통해 상자들을 비내림차순으로 정렬합니다. 한 번의 마법 교환에서, 마술사는 $a_i$와 $a_{i+1}$의 이진수 표현이 정확히 한 비트만 차이 나는 인덱스 $i$ ($1 \le i < N$)를 선택하여 $a_i$와 $a_{i+1}$의 위치를 바꿉니다.

공연을 지켜보던 Busy Beaver는 이 마술의 한계에 대해 궁금해졌습니다. 상자에 들어갈 수 있는 $a_1, a_2, \dots, a_N$의 모든 가능한 초기값 $2^{MN}$개 중에서, 마법 교환을 사용하여 비내림차순으로 정렬할 수 있는 경우는 몇 가지일까요? 이 수는 매우 클 수 있으므로, Busy Beaver는 그 수를 $10^9 + 7$로 나눈 나머지를 구하고자 합니다.

입력

입력의 첫 번째이자 유일한 줄에는 두 정수 $N$과 $M$ ($1 \le N, M \le 50$)이 주어집니다.

출력

마법 교환을 사용하여 정렬할 수 있는 수열의 개수를 $10^9 + 7$로 나눈 나머지를 하나의 정수로 출력하십시오.

서브태스크

이 문제에는 다섯 개의 서브태스크가 있습니다.

• (10점): $1 \le N, M \le 5$.
• (20점): $1 \le M \le 4$.
• (10점): $1 \le M \le 10$.
• (10점): $1 \le M \le 15$.
• (50점): 추가 제약 조건 없음.

예제

입력 1

3 2

출력 1

44

입력 2

50 1

출력 2

898961331

입력 3

10 10

출력 3

649370314

참고

첫 번째 예제에서 마법 교환을 사용하여 정렬할 수 있는 수열 중 하나는 $[a_1, a_2, a_3] = [3, 1, 2]$이며, 과정은 다음과 같습니다.

1. $i = 1$을 선택합니다. $a_1 = 3$과 $a_2 = 1$은 이진수 표현에서 정확히 한 비트만 차이 나므로, 이는 마법 교환입니다. 수열은 $[1, 3, 2]$가 됩니다.
2. $i = 2$를 선택합니다. $a_2 = 3$과 $a_3 = 2$는 이진수 표현에서 정확히 한 비트만 차이 나므로, 이는 마법 교환입니다. 수열은 $[1, 2, 3]$이 되며, 이는 비내림차순입니다.

가능한 모든 초기 수열 $2^{3 \cdot 2} = 64$개 중 44개의 수열을 마법 교환을 통해 정렬할 수 있습니다.