27743번 - 어려운 하노이 탑 서브태스크

하노이 탑은 다음 규칙을 지키면서, 첫 번째 막대기에 꽂힌 원판들을 그 순서 그대로 세 번째 막대기로 옮기는 놀이다.

1. 한 번에 $1$개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 원판 위에 자신보다 크기가 큰 원판을 올릴 수 없다. 반대로 말해서 크기가 작거나 같은 원판은 올릴 수 있다.

위 규칙에 따라 원판을 옮기려고 한다. 크기가 $i$인 원판이 $M$개 존재하고 각각 $1$번부터 $M$번까지 번호가 매겨져 있다. $(1 \le i \le N,$ $i$는 정수$)$

첫 번째 막대기에 원판이 크기 내림차순으로, 크기가 같다면 번호 내림차순으로 쌓여있을 때, 쌓인 순서 그대로 세 번째 막대기로 옮기기 위한 이동 횟수의 최솟값을 구하시오.

위 그림은 $N = 3$ 일 때의 모습이다.

첫 번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다.

이동 횟수의 최솟값을 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 \le N, M \le 3 \times 10^9$