시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB22417114181.977%

문제

$N \times M$ 크기의 백지 퍼즐 격자가 주어진다. 격자의 각 칸에는 퍼즐 조각을 끼울 수 있으며, 조각의 각 면은 볼록하거나, 오목하거나, 평평할 수 있다. 조각은 회전을 고려하지 않으며, 총 $3^4 = 81$가지이다.

각 형태의 조각을 수량 제한 없이 사용 가능할 때, 격자를 채우는 방법의 수를 $10^9+7$로 나눈 나머지를 계산하라. 하나 이상의 칸에 다른 형태의 조각을 끼울 경우, 다른 방법으로 취급한다.

입력

첫 번째 줄에 두 정수 $N$과 $M$이 차례대로 주어진다. ($1 \le N \le 8$, $1 \le M \le 10^5$)

출력

첫 번째 줄에 답을 출력한다.

예제 입력 1

2 2

예제 출력 1

81

예제 입력 2

1 2

예제 출력 2

3

예제 입력 3

8 8

예제 출력 3

889639405