| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 224 | 171 | 141 | 81.977% |
$N \times M$ 크기의 백지 퍼즐 격자가 주어진다. 격자의 각 칸에는 퍼즐 조각을 끼울 수 있으며, 조각의 각 면은 볼록하거나, 오목하거나, 평평할 수 있다. 조각은 회전을 고려하지 않으며, 총 $3^4 = 81$가지이다.
각 형태의 조각을 수량 제한 없이 사용 가능할 때, 격자를 채우는 방법의 수를 $10^9+7$로 나눈 나머지를 계산하라. 하나 이상의 칸에 다른 형태의 조각을 끼울 경우, 다른 방법으로 취급한다.
첫 번째 줄에 두 정수 $N$과 $M$이 차례대로 주어진다. ($1 \le N \le 8$, $1 \le M \le 10^5$)
첫 번째 줄에 답을 출력한다.
2 2
81
1 2
3
8 8
889639405